# 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

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

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

&#x20;                                   dp\[i] = max(dp\[i-1] + input\[i], input\[i])\\

Output 1:

```java
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:&#x20;

need to maintain current leftIndex and global leftIndex+rightIndex

```java
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};
}
```

\\
