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

示例:

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

进阶:

如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

Solution

参考：《算法小抄》2.3

• 动态规划
• 以 nums[i] 为结尾的最大子数组和为 dp[i]

# @lc code=start
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n=len(nums)
        if n==0: return 0
        dp = [0]*n
        dp[0]=nums[0]
        for i in range(1,n):
            dp[i]=max(nums[i],nums[i]+dp[i-1])
        res = float('-inf')
        for i in range(n):
            res=max(res,dp[i])
        return res
# @lc code=end

• 进行“状态压缩”优化（ dp[i] 仅与 dp[i-1] 有关）

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n=len(nums)
        if n==0: return 0
        dp_pre=nums[0]
        dp=0
        res=dp_pre
        
        for i in range(1,n):
            dp=max(nums[i], nums[i]+dp_pre)
            dp_pre=dp
            res=max(res, dp)
        return res

cpp

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;
        vector<int> dp(n, 0); // 以 nums[i] 结尾的最大子数组和
        dp[0] = nums[0];
        for (int i = 1; i < n; ++i) {
            dp[i] = max(dp[i-1] + nums[i], nums[i]);
        }
        return *max_element(dp.begin(), dp.end());
    }
};

参考 代码随想录

• 贪心算法

• 局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。

• 全局最优：选取最大“连续和”

• 「局部最优的情况下，并记录最大的“连续和”，可以推出全局最优」。

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