53. 最大子序和 Krains 2020-08-20 10:46:24 动态规划前缀和

class Solution {
    public int maxSubArray(int[] nums) {
        int sum = 0;
        // 前缀和中需要添加一个0，这里直接初始化min为0
        int min = 0;
        int ans = nums[0];
        for(int i = 0; i < nums.length; i++){
            sum += nums[i];
            ans = Math.max(sum-min, ans);
            min = Math.min(sum, min);
        }
        return ans;
    }
}

class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int dp = nums[0];	// 用dp存状态
        int ans = nums[0];
        for(int i = 1; i < n; i++){
            // nums[i]加入dp代表的子数组的和与
            // 单独nums[i]为子数组的和相比较，取较大者
            dp = Math.max(nums[i], dp + nums[i]);
            ans = Math.max(ans, dp); 
        }
        return ans;
    }
}