最大子序和

题目

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

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

具体思路

• 从头记录，如果当前加值小于0，重新开始计算
• 如果大于，可以继续加，并与最大值进行比较

代码

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int res = INT_MIN;
        int cur = 0;
        for (int i = 0; i < nums.size(); i++) {
            cur += nums[i];
            if (cur > res)
                res = cur;
            if (cur < 0)
                cur = 0;
        }
        return res;
    }
};

Java

class Solution {
    public int maxSubArray(int[] nums) {
        int res = nums[0];
        int cur = 0;
        for (int i = 0; i < nums.length; i++) {
            // if (cur >= 0) {
            //     cur += nums[i];
            // } else {
            //     cur = nums[i];
            // }
            cur =  cur >= 0 ? cur + nums[i] : nums[i];
            res = Math.max(cur, res);
        }
        return res;
    }
}

动态规划

求 0 − n 的最大连续数组长度： f ( i ) = M a x [ ( f ( i − 1 ) , f ( i − 1 ) + n u m s [ i ] ]

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