Maximum Sum SubArray

Question

I am trying to find the contiguous subarray within an array which has the largest sum. So, for the array

{5, 15, -30, 10, -5, 40, 10}

the maximum sum possible using those numbers contiguously would be 55, or (10 + (-5) + 40 + 10) = 55. The program below outputs the maximum sum of 55, however, the problem I am trying to figure out is how to print the sequence that produces this 55. In other words, how can I print out the 10, -5, 40, and 10?

public static void main(String[] args) {
    int[] arr = {5, 15, -30, 10, -5, 40, 10};

    System.out.println(maxSubsequenceSum(arr));         
}

public static int maxSubsequenceSum(int[] X) {
    int max = X[0];
    int sum = X[0];

    for (int i = 1; i < X.length; i++) {
        sum = Math.max(X[i], sum + X[i]);
        max = Math.max(max, sum);
    }
    return max;
}

I was thinking of creating an ArrayList to store the sum values at every index of i, so the ArrayList would look like (5, 20, -10, 10, 5, 45, 55). And then I was planning on clearing the ArrayList from index 0 to the first negative number in the list, however, this only solves the problem for this specific example, but if I change the original array of numbers, this solution won't work.

Answer 1

You can replace Math.Max functions by if statements and update start and end index of the best subarray. Pascal version:

    if X[i] > sum + X[i] then begin
        sum := X[i];
        start := i;
      end
      else
        sum := sum + X[i];
      if max < sum then begin
        max := sum;
        finish := i;
      end;

Answer 2

You can track the starting and ending indexes of the current best subarray in your loop. Instead of using max() to compute sumand max, just do the following :

int sum_start = 0, sum_end = 0, start = 0, end = 0;
// In the for loop
if (X[i] > sum + X[i]) {
    sum = X[i];
    sum_start = i;
    sum_end = i;
} else {
    ++sum_end;
}
if (sum > max) {
    start = sum_start;
    end = sum_end;
    max = sum;
}

Answer 3

there is an o(n) solution, a single for loop through the array and reset your sub-sequence whenever your current total is below 0.

{5, 15, -30, 10, -5, 40, 10}

• 5 + 15 = 20
• 20 - 30 = -10 (reset sub-sequence)
• 10 -5 +40 +10 = 55
• end. 55 is max sub-sequence

edit: to get subsequence... whenever you change max, update your subsequence

• current left index changes only when u reset
• current right index changes every iteration
• new max -> save current left and right index...