动态规划系列-子数组最大和

子数组最大和—题目描述

输入一个 非空 整型数组，数组里的数可能为正，也可能为负。

数组中一个或连续的多个整数组成一个子数组。

求所有子数组的和的最大值。

要求时间复杂度为O(n)。

样例
输入：[1, -2, 3, 10, -4, 7, 2, -5]

输出：18

子数组最大和—思路

子数组的最大值，这是一个求最值问题，十有八九使用动态规划。【这个是我们的经验-求最值问题，十有八九使用动态规划】

拿到一个问题，我们首先要去思考他的解空间有多大？又或者说，计算机用最笨的方法去枚举的话，最多需要枚举多少次。

所有的子数组和的最大值，我需要枚举start, end, 解空间有$n^2$

接着我们再来回答我们接下来要做什么？ 我们需要去检查这一组解是否是最优解。
如何判断呢？ 这个是一个判定问题。

对这个题目而言，我们的解决步骤如下：
从start到end累加得到一个数，累加的时间复杂度是$O(N)$

最终的时间复杂度是$O(n^3)$

动态规划思路

一维最大子数组和	最大子数组和系列
问题描述	给定一个整数数组 nums 计作$A_i$，找到一个具有最大和的子数组（子数组最少包含一个元素），返回其最大和
状态表示	F[i]表示利用以$A_i$结尾的子数组的最大和
转移方程	$F[i]=\begin{cases}F[i-1]+A[i] & \text{if } F[i-1] \gt 0 \\ A[i] & \text{if } F[i-1] \le 0 \end{cases}$
边界	F[0]=0
目标	F[N]
空间压缩	由于仅与前一项有关，所以可以用一个变量来代替

子数组最大和—代码

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        /*
        dp[i] = num[i] if dp[i - 1] < 0; 
        dp[i] = dp[i - 1] + num[i]; if dp[i - 1] >= 0
        表示以A[i]结尾的子数组的子数组最大和。
        最终的结果，一定是dp[i]中选择一个最大的。
        */
        
        int sum = 0;
        int res = INT_MIN;
        for (int i = 0; i < nums.size(); ++i) {
            if (sum < 0) {
                sum = nums[i];
            }
            else {
                sum += nums[i];
            }
            
            res = max(res, sum);
        }
        
        return res;
    }
};