原文链接：数据结构001：最大子数组和
给你一个整数数组
nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组 是数组中的一个连续部分。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
- 1
- 2
- 3
示例 2：
输入：nums = [1] 输出：1
- 1
- 2
示例 3：
输入：nums = [5,4,-1,7,8] 输出：23
- 1
- 2
要求字数组中和最大的那组对应的和，首先能想到的是完全遍历，使用暴力求解的方法，确实可以解决问题，但有没有更简单一点的方法呢？答案肯定是有的（这话貌似很是废话）。换种思路，如果针对元素数量较少的数组，我们使用完全遍历，貌似没有什么压力，因此，我们不妨从简单的数组子数组入手，看看能不能发现什么规律。
下面我们以数组{a, b, c, d, e}为例，列举出其所有连续的子序列：
分析该问题，我们要找软柿子捏，首先分析1，以a结尾的子数组和最大值为
f
a
−
m
a
x
=
a
(1)
f_{a-max}=a \tag1
fa−max=a(1)
对于2，以b结尾的子数组和最大值为
f
b
−
m
a
x
=
m
a
x
{
a
+
b
,
b
}
=
m
a
x
{
f
a
−
m
a
x
+
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结尾的子数组和最大值为
f
c
−
m
a
x
=
m
a
x
{
a
+
b
+
c
,
b
+
c
,
c
}
=
m
a
x
{
f
b
−
m
a
x
+
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)
依次类推：
f
d
−
m
a
x
=
m
a
x
{
a
+
b
+
c
+
d
,
b
+
c
+
d
,
c
+
d
,
d
}
=
m
a
x
{
f
c
−
m
a
x
+
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)
f e − m a x = m a x { a + b + c + d + e , b + c + d + e , c + d + e , d + e , e } = m a x { f d − m a x + 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}中连续子序列和最大值为
m
a
x
{
f
a
−
m
a
x
,
f
b
−
m
a
x
,
f
c
−
m
a
x
,
f
d
−
m
a
x
,
f
e
−
m
a
x
}
(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)
对于数组
n
u
m
s
nums
nums，我们设
f
(
i
)
f(i)
f(i)为以第
i
i
i个元素结尾的连续子数组和最大值，则有：
f
(
i
)
=
m
a
x
{
f
(
i
−
1
)
+
n
u
m
s
[
i
]
,
n
u
m
s
[
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
<
i
<
n
0
m
a
x
{
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<int>& nums) {
int pre = 0, maxAns = nums[0];
for (const auto &x: nums) {
pre = max(pre + x, x);
maxAns = max(maxAns, pre);
}
return maxAns;
}