1.3 Largest Subarray Sum

Assumption: given array is not null and length >= 1

Input: int[] array

Output 1: int the largest subarray sum

Output 2: int[] {leftIndex, rightIndex, the largest subarray sum}

Solution:

1. Base case: dp[0] = input[0]

2. Option 1: input[i] as the new starting point for the sum

Option 2: Inherit from dp[i-1], discard all previous values, because dp[i] will be the new max sum → able to optimize space

3. Induction rule: dp[i] represents in [0, ith] index, the largest sum of the subarray ends at ith index

dp[i] = max(dp[i-1] + input[i], input[i])

Output 1:

public int largestSum (int[] array) {
  int lastMax = array[0];
  int globalMax = array[0];
  for (int i = 1; i < array.length; i++) {
    lastMax = Math.max(lastMax + array[i], array[i]);
    globalMax = Math.max(globalMax, lastMax);
  }
  return globalMax;
}

Output 2:

need to maintain current leftIndex and global leftIndex+rightIndex

public int[] largestSum (int[] array) {
  int curSum = array[0];
  int globalSum = array[0];
  int globalLeft = 0;
  int globalRight = 0;
  int curLeft = 0;
  for (int i = 1; i < array.length; i++) {
    if (curSum < 0) {
      curSum = array[i];
      curLeft = i;
    } else {
      curSum += array[i];
    }

    if (curSum > globalSum) {
      globalLeft = curLeft;
      globalRight = i;
      globalSum = curSum;
    }
  }
  return new int[] {globalLeft, globalRight, globalSum};
}