算法日记-LeetCode-53.最大子数组和

原题链接：53. 最大子数组和 - 力扣（LeetCode）

题目大意

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分

解题思路

动态规划

明确定义：

我们可以通过dp数组记录，dp[i]表示以下标i结尾的「连续子数组的最大和」，记为f(i)，那么要求到i + 1结尾的连续子数组的最大和，只要比较nums[i + 1]，f(i) + nums[i+ 1]，取他们中的最大值即可。

状态转移方程：dp[i + 1] = Math.max(dp[i] + num[i + 1], num[i + 1])

最后，取整个dp数组的最大值，即为所求的结果

简化写法

由于f(i)的值只与f(i - 1)有关，所以可以用一个值来记录，表示f(i)和f(i - 1)的关系

f(i) = f(i - 1) + num[i]，可以通过变量的形式，将这一个关系维持到遍历结束

代码

class Solution {
    public int maxSubArray(int[] nums) {
        int pre = 0, max = nums[0];
        for (int num : nums) {
            pre = Math.max(pre + num, num);
            max = Math.max(pre, max);
        }
        return max;
    }
}