Given an unsorted integer array, find thesubarraythat has the greatest sum. Return the sum.

Assumptions

• The given array is not null and has length of at least 1.

Examples

• {2, -1, 4, -2, 1}, the largest subarray sum is 2 + (-1) + 4 = 5

• {-2, -1, -3}, the largest subarray sum is -1

Solution: prefix sum，largest subarray sum = 当前sum - smallest previous subarray sum，每次更新max和min

  public int largestSum(int[] array) {
    int min = 0, max = array[0], preSum = 0;
    for (int num : array) {
      preSum += num;
      max = Math.max(max, preSum - min);
      min = Math.min(min, preSum);
    }
    return max;
  }

或: 若prevSum > 0，则取prevSum + array[i]，否则取array[i]