Thread: Find largest subsequence sum

Give efficient algorithm to find largest subsequence sum in an array.

I think that the following algorithm solves the problem in linear time. But it should be checked. "x" is the array of numbers and "n" is the number of elements in the array. Array is assumed to be 0-indexed. -9999999999 is used for -Inf and it should be changed with true -Inf constant. "maxv" is the maximum sum and "maxi1" and "maxi2" is the start and end indices of the sub-array.

The idea behind the algorithm is as follows:
It uses cumulative sum instead of the original array. Then at each index, it calculates the difference of the value at that index and the smallest value before that index. The maximum sub-array must have this value maximized. Two loops are merged into a single loop. After one pass over the numbers, we have the largest sum and boundary indices of the sub-array. So dynamic programming method is used.

Code:

    mini = -1;    minv = 0;    maxi1 = 0;    maxi2 = 0;     maxv = -9999999999;   
    for (i=0;i<n;i++) {
        if (i>0)
            x[i] += x[i-1];
        if (x[i]-minv>=maxv) {
            maxv = x[i]-minv;
            maxi1 = mini+1;
            maxi2 = i;
        }
        if (x[i]<minv) {
            minv = x[i];
            mini = i;
        }
    }

Just Add all positive elements of the array