最大子序和

时间复杂度 $O(n)$, 空间复杂度 $O(1)$

Java 代码

class Solution {
    public int maxSubArray(int[] nums) {
        int s = 0;        // 前缀和
        int smin = 0;     // 前缀和的最小值
        int res = Integer.MIN_VALUE; // 结果
        for (int i : nums) {
            smin = Math.min(smin, s);
            s += i;
            res = Math.max(res, s - smin);
        }
        return res;
    }
}