动态规划解决子列和问题

题目链接-来源：力扣（LeetCode）

输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为O(n)。

示例1:

输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

思路：

我们希望在O(n)的复杂度内完成最大值的计算，那么就需要在每一次考察新元素的时候充分利用已有元素信息，自然想到动态规划。
记dp[i]表示「截至第i个元素，数组中出现的子数组和的最大值」，这样我们每次同步更新一个 dp[i] 的最大值，直到数组末尾，代表的意义就是题目所要求的结果。
递推规则：考察dp[i - 1]是否大于0。若 dp[i - 1] <= 0，证明前驱的子数组对我们增大子数组和没有帮助，我们就舍弃之，只留下 nums[i] 的值供后续子数组参考；否则，我们留下 dp[i - 1] 的值，加上 nums[i] 的值，构成当前位置的 dp[i]。
每次更新 dp，维护一个最大值，最后返回即可。
时间复杂度：O(n)
空间复杂度：O(n)

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = nums[0];
        int max = dp[0];
        for (int i = 1; i < n; i++) {
            dp[i] = nums[i] + (dp[i - 1] <= 0 ? 0 : dp[i - 1]);
            max = (max < dp[i])? dp[i] : max;
        }
        
        return max;
    }
}