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 {x₁,x₂,...,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₁,...,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₂ = 5, while V₂ = 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₃ = 5-1+2 = 6, S₂ = 5 and S₃ = V₃ = 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 });  
      }  
 }