53-最大子序和

力扣53

https://leetcode-cn.com/problems/maximum-subarray/

子序dp系列真的很顶

看[4,-1,2]部分，可以观察出这部分最大子序和是5，要得到5，所以dp[i] = dp[i - 1] + nums[i]
看[-2,1]，最大子序和应该直接取1，也就是加了不如不加，因为不如当前的，所以是dp[i] = max(dp[i-1] + nums[i], nums[i])
想一想就知道需要不一样的两段之间比大小，所以不是一直累加dp，而是要max变量记录

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

其他动态规划的题目可以点击这里

# 力扣