53 最大子数组和

一、题目

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

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

二、题解

2.1 贪心法

思路：若当前指针所指元素之前的和小于0，则丢弃当前元素之前的数列

class Solution {
    public int maxSubArray(int[] nums) {
        int maxSum = nums[0], preSum = nums[0];
        for(int i = 1; i < nums.length; i++) {
            if (preSum < 0) {
                preSum = nums[i];
            } else {
                preSum += nums[i];
            }
            maxSum = maxSum > preSum ? maxSum : preSum;
        }
        return maxSum;
    }
}

时间复杂度：$O(n)$

空间复杂度：$O(1)$

2.2 动态规划

思路：若前一个元素大于0，则将其加到当前元素上

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

时间复杂度：$O(n)$

空间复杂度：$O(1)$