#

class Solution {
    public int maxSubArray(int[] nums) {
        int pre = 0;
        int maxPre = nums[0];
        for (int i = 0; i < nums.length; i++) {
            pre = Math.max(pre + nums[i], nums[i]);
            if (pre > maxPre)
                maxPre = pre;
        }
        return maxPre;
    }
}

前缀和解法

由于子数组的元素和等于两个前缀和的差，所以将数组转化为前缀和数组，问题就变成 121. 买卖股票的最佳时机 了。

[−2,1,−3,4,−1,2,1,−5,4] 👉 [0, −2, -1,−4, 0, −1, 1, 2, −3, 1]

本题子数组不能为空，相当于一定要交易一次。

class Solution {
    public int maxSubArray(int[] nums) {
        int profit = Integer.MIN_VALUE;     // 最小值，则for中必买一次
        int minPreSum = 0;      // 最低价格。即前缀和中的第一个元素 0
        int preSum = 0;     
        for (int x : nums) {
            preSum += x; // 当前的前缀和，相当于股票今日价格
            profit = Math.max(profit, preSum - minPreSum); // 减去前缀和的最小值
            minPreSum = Math.min(minPreSum, preSum); // 维护前缀和的最小值
        }
        return profit;
    }
}