LeedCode 53.最大子序列和（简单） —— 动态规划

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

代码来源于leedcode官方

思路：

从头开始，每次更新pre，看是否要加上之前的最大和，如果是负数则没必要加，如果是正数则加上。

每次更新maxAns，看当前的最大值是否比之前的最大值大。大则更新。

就是看前一个元素是否大于0，如果大于0就把前一个元素加到当前元素上，最后返回当前数组的最大值即可。

复杂度

时间复杂度：O(n)，其中 n 为 nums 数组的长度。我们只需要遍历一遍数组即可求得答案。
空间复杂度：O(1)。我们只需要常数空间存放若干变量。