原文链接：数据结构001：最大子数组和

题目

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

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

示例 1：

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

示例 2：

输入：nums = [1]
输出：1

示例 3：

输入：nums = [5,4,-1,7,8]
输出：23

解题思路

要求字数组中和最大的那组对应的和，首先能想到的是完全遍历，使用暴力求解的方法，确实可以解决问题，但有没有更简单一点的方法呢？答案肯定是有的（这话貌似很是废话）。换种思路，如果针对元素数量较少的数组，我们使用完全遍历，貌似没有什么压力，因此，我们不妨从简单的数组子数组入手，看看能不能发现什么规律。

下面我们以数组{a, b, c, d, e}为例，列举出其所有连续的子序列：

1. 以a结尾的子数组{a}；
2. 以b为结尾的子数组{a, b}、{b}；
3. 以c为结尾的子数组{a, b, c}、{b, c}、{c}；
4. 以d为结尾的子数组{a, b, c, d}、{b, c, d}、{c, d}、{d}；
5. 以e为结尾的子数组{a, b, c, d, e}、{b, c, d, e}、{c, d, e}、{d, e}、{e}。

分析该问题，我们要找软柿子捏，首先分析1，以a结尾的子数组和最大值为
fa−max=a(1)f_{a-max}=a \tag1 fa−max​=a(1)
对于2，以b结尾的子数组和最大值为
fb−max=max{a+b,b}=max{fa−max+b,b}(2)f_{b-max}=max\{a+b, b\}\\=max\{ f_{a-max}+b, b\} \tag2 fb−max​=max{a+b,b}=max{fa−max​+b,b}(2)
对于3，以c结尾的子数组和最大值为
fc−max=max{a+b+c,b+c,c}=max{fb−max+c,c}(3)f_{c-max}=max\{a+b+c, b+c, c\}\\ =max\{f_{b-max}+c, c\} \tag3 fc−max​=max{a+b+c,b+c,c}=max{fb−max​+c,c}(3)
依次类推：
fd−max=max{a+b+c+d,b+c+d,c+d,d}=max{fc−max+d,d}(4)f_{d-max}=max\{a+b+c+d, b+c+d, c+d, d\}\\ =max\{f_{c-max}+d, d\} \tag4 fd−max​=max{a+b+c+d,b+c+d,c+d,d}=max{fc−max​+d,d}(4)

fe−max=max{a+b+c+d+e,b+c+d+e,c+d+e,d+e,e}=max{fd−max+e,e}(5)f_{e-max} =max\{a+b+c+d+e, b+c+d+e, c+d+e, d+e, e\} \\ =max\{f_{d-max}+e, e\} \tag5 fe−max​=max{a+b+c+d+e,b+c+d+e,c+d+e,d+e,e}=max{fd−max​+e,e}(5)

由公式1-5可得，数组{a, b, c, d, e}中连续子序列和最大值为
max{fa−max,fb−max,fc−max,fd−max,fe−max}(6)max\{f_{a-max}, f_{b-max}, f_{c-max}, f_{d-max},f_{e-max}\} \tag6 max{fa−max​,fb−max​,fc−max​,fd−max​,fe−max​}(6)

对于数组numsnumsnums，我们设f(i)f(i)f(i)为以第iii个元素结尾的连续子数组和最大值，则有：
f(i)=max{f(i−1)+nums[i],nums[i]}(7)f(i)=max\{ f(i-1)+nums[i],nums[i]\} \tag7 f(i)=max{f(i−1)+nums[i],nums[i]}(7)
其中0 max{f(0),f(1),...,f(n−1)}(8)max\{f(0), f(1), ..., f(n-1) \} \tag8 max{f(0),f(1),...,f(n−1)}(8)
因此，此题代码实现如下：

int maxSubArray(vector& nums) {int pre = 0, maxAns = nums[0];for (const auto &x: nums) {pre = max(pre + x, x);maxAns = max(maxAns, pre);}return maxAns;
}