复杂度 $O(n)$

1. $f(i)$表示“只考虑前$i$个数且以$a_i$结尾的连续子数组的选法集合”，属性：总和$Max$
2. 状态计算
   • $a_i$自成一个子数组，即$f(i)=a_i$
   • $a_i$接在$a_{i-1}$后面，拓展原有子数组，即$f(i)=f(i-1)+a_i$
   • 综上：$f(i) = max(a_i, f(i-1)+a_i) = max(0, f(i-1)) + a_i$

代码

class Solution {
    public int maxSubArray(int[] nums) {
        int[] f = new int[nums.length];
        f[0] = nums[0];
        int res = f[0];
        for (int i = 1; i < nums.length; i++) {
            f[i] = Math.max(0, f[i - 1]) + nums[i];
            res  = Math.max(res, f[i]);
        }
        return res;
    }
}

空间略微优化

class Solution {
    public int maxSubArray(int[] nums) {
        int res = nums[0], f = nums[0];  // 要求子数组非空 故res初始为首个元素的值
        for (int i = 1; i < nums.length; i++) {
            f = Math.max(0, f) + nums[i];
            res = Math.max(res, f);
        }
        return res;
    }
}