## Tuesday, April 10, 2012

### Maximum Consecutive Sum

This is a text-book dynamic programming problem, but it's still interesting since many job interview questions have the same level of complexity. You are given a sequence of numbers {x1,x2,...,xn} 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 Sk-1 as the maximum consecutive sum for the sequence {x1,...,xk-1} and Vk-1 as the maximum consecutive sum for the same array including xk-1. Note that Sk-1 and Vk-1 are in general distinct, e.g., for {5,-1,2,-2,1}, S2 = 5, while V2 = 5-1 = 4. The values of Vk and Sk can be computed using dynamic programming. In fact, Vk = max(Vk-1+xk,xk) and Sk = max(Sk-1,Vk). E.g., for {5,-1,2,-2,1}, V3 = 5-1+2 = 6, S2 = 5 and S3 = V3 = 6. At each step we only need Sk-1 and Vk, so we only store two variables. The problem has optimal substructure because the optimal solution Sk can be found by using the optimal solution Sk-1 of a sub-problem together with the additional information stored in Vk.
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 Vk, call it m, and of the two indices that define Sk, say i,j. To keep track of m, we just need to notice that if xk > Vk-1+xk then m = k, otherwise m is unchanged; similarly, to keep track of i,j, if Vk > Sk-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=V=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 });
}
}
``````