题目描述

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

样例

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

算法1

(动态规划) $O(n)$

1.状态表示：f（i）集合：以nums[i]结尾的所有连续子序列中的max
2.状态计算：划分为两种情况：1）f（i-1)<0，f(i) = nums[i];
2)f(i-1)>0,f(i) = f(i-1)+nums[i];
状态转移方程：f（i） =max（ f（i-1）+nums[i],nums[i]);
最后计算f（i）中最大值为答案

参考文献

C++ 代码

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> res(n);
        res[0] = nums[0];
        for(int i = 1;i<n;i++){
            res[i] = max(res[i-1]+nums[i],nums[i]);
        }
        int cmax = INT_MIN;
        for(int i = 0;i<n;i++){
            cmax = max(cmax,res[i]);
        }
        return cmax;
    }
};

算法2

(贪心) $O(n)$

每次得到当前序列的最大连续子序列和，如果nums[i]大于ans,就从新获取

参考文献

C++ 代码

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int cursum = 0,res = INT_MIN;
        for(auto u:nums){
            cursum = max(cursum+u,u);
            res = max(cursum,res);
        }
        return res;
    }
};