Continuous Subarray Sum

出处

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

Solution

只观察以当前节点为末节点可能的最大sum,并记录一个global sum。对于当前节点,需要判断加入对应数组元素能否使得sum变大。递推公式如下

sum[i] = max(sum[i-1] + A[i], A[i])

因为需要连续的子数组,故计算当前的最大sum,只在乎前一次计算的结果,因此用一个变量每次覆盖即可 (正如我们之前关于简化DP空间的描述)。

Complexity

遍历一次,时间复杂度 O(n),空间复杂度可以优化至 O(1)

Code

int largestSum(int[] arr){
    int len = arr.length;
    if (len == 0) return 0;
    int maxSum = arr[0];
    int sum = arr[0];
    for (int i = 1; i < len; i++){
        sum = Math.max(sum + arr[i], arr[i]);
        if (sum > maxSum){
            maxSum = sum;
        }
    }
    return maxSum;
}