_{1},x

_{2},...,x

_{n}} and are asked to compute the maximum consecutive sum in the array. For example, the maximum consecutive sum in {1,-3,7} is 1-3+7 = 5; in {5,-1,2,-2,1} it's 5-1+2 = 6.

Now let's look at the optimal substructure of the problem. Let's define S

_{k-1}as the maximum consecutive sum for the sequence {x

_{1},...,x

_{k-1}} and V

_{k-1}as the maximum consecutive sum for the same array including x

_{k-1}. Note that S

_{k-1}and V

_{k-1}are in general distinct, e.g., for {5,-1,2,-2,1}, S

_{2}= 5, while V

_{2}= 5-1 = 4. The values of V

_{k}and S

_{k}can be computed using dynamic programming. In fact, V

_{k}= max(V

_{k-1}+x

_{k},x

_{k}) and S

_{k}= max(S

_{k-1},V

_{k}). E.g., for {5,-1,2,-2,1}, V

_{3}= 5-1+2 = 6, S

_{2}= 5 and S

_{3}= V

_{3}= 6. At each step we only need S

_{k-1}and V

_{k}, so we only store two variables. The problem has optimal substructure because the optimal solution S

_{k}can be found by using the optimal solution S

_{k-1}of a sub-problem together with the additional information stored in V

_{k}.

Finally, if we want to know the indices at which to start and end the sum, we need to keep track of the initial index to compute the sum V

_{k}, call it m, and of the two indices that define S

_{k}, say i,j. To keep track of m, we just need to notice that if x

_{k}> V

_{k-1}+x

_{k}then m = k, otherwise m is unchanged; similarly, to keep track of i,j, if V

_{k}> S

_{k-1}, then i = m and j = k, otherwise i,k are unchanged.

Here's a very straight forward java implementation of this algorithm with a few test cases. Enjoy!

```
public class MaximumConsecutiveSum {
public int maximumConsecutiveSum(int[] x) {
// initialize S[0]=V[0]=0
int runningMaxConsSum = 0, maxConsSumRightEdgeIncl = 0;
// left is the starting index for V[k], start,end the indices for S[k]
int left = 0, start = 0, end = 0;
for (int k = 0; k < x.length; k++) {
int tmp = maxConsSumRightEdgeIncl + x[k];
if (tmp > x[k])
maxConsSumRightEdgeIncl = tmp;
else {
maxConsSumRightEdgeIncl = x[k];
left = k;
}
if (maxConsSumRightEdgeIncl > runningMaxConsSum) {
runningMaxConsSum = maxConsSumRightEdgeIncl;
start = left;
end = k;
}
}
System.out.println("[" + start + "," + end + "]: " + runningMaxConsSum);
return runningMaxConsSum;
}
public static void main(String[] args) {
MaximumConsecutiveSum maxSum = new MaximumConsecutiveSum();
maxSum.maximumConsecutiveSum(new int[] { 2, -1, 3 });
maxSum.maximumConsecutiveSum(new int[] { 2, -8, 3 });
maxSum.maximumConsecutiveSum(new int[] { 5, -1, 2, -2, 1 });
maxSum.maximumConsecutiveSum(new int[] { 5, -8, 2, -2, 2, 5, 1, 6, 1, 2 });
maxSum.maximumConsecutiveSum(new int[] { 3, -9, 2, 9, 12 });
}
}
```

## No comments:

## Post a Comment