给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组是数组中的一个连续部分。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
输入：nums = [1]
输出：1
<1>我的思路是这样的，利用双指针的方法，
两个指针，一个指针a,一个指针b,指针a指向开头的元素，指针b指向a的下一个，先进行一个判断，如果指针a+b<b说明a肯定是个负数，这样的话最大连续子序列肯定是不包含a的，比如-1，-2，2，1，一开始a=-1,b=-2,a+b<b,序列包含a只会变小，指针移动，变为a=-2,b=2,a+b<b,指针再移动，a=2,b=1,a+b>b
之后在进行判断一下如果a+b的值是>0的，那么对b指针后面的元素来说，a,b指向的元素是有利于序列的和变大的，b指针后移，直到a指针到b指针之间的元素的和<=0,或者b指针走到了尽头。
代码如下：
class Solution {
public:
int maxSubArray(vector<int>& nums) {
vector<int> *p = &nums;
auto end = nums.end();
vector<int>::iterator a = p->begin();
vector<int>::iterator b = a;
b++;
int num = *a;
int max = *a;
while (b != end) {
while (*a + *b < *b) {
a = b;
b++;
num = *a;
if (max < num)
max = num;
if (b == end)
return max;
}
while (b != end&&num + *b >0) {
num += *b;
if (max < num)
max = num;
b++;
}
if (b != end) {
num += *b;
if (max < num)
max = num;
a++;
b = a;
b++;
num = *a;
if (max < num)
max = num;
}
}
return max;
}
};
可以看到这个代码是比较麻烦的，而且写到后期，我自己的思路其实是有一些不清楚了。。。
<2>官方的思路1——动态规划的方法
我之前是不太了解动态规划，唯一的感觉就是难！思路感觉和我的方法的思路是有一丢丢的相似，会判断每一个元素的之前的序列的和的最大值以及加上当前的元素的最大值
，比如序列为 -2，1，-1，-3，4，1，-1，2，-5，4
第一个元素-2之前的序列和为0，加上当前的元素，序列和为-2，之前的最大的序列和也是-2，第二个元素1，之前的序列和为-2，当前的元素为1，当前的序列和为-1，最大的序列和为1，以此类推，最大和的序列为：
-2 1 -1 -3 4 1 -1 2 -5 4
-2 1 0 -3 4 5 4 6 1 5
因此我们只需要求出每个位置的 f(i)，然后返回 f 数组中的最大值即可。那么我们如何求 f(i) 呢？我们可以考虑 ums[i] 单独成为一段还是加入 f(i-1) 对应的那一段，这取决于 nums[i] 和 f(i−1)+nums[i] 的大小，我们希望获得一个比较大的，于是可以写出这样的动态规划转移方程：
代码如下：
class Solution {
public:
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;
}
};
可以看出代码不仅简洁了很多，思路也清晰了很多！自己还是比较缺乏这方面的锻炼。
<3>官方的思路2——分治
我们定义一个操作 get(a, l, r) 表示查询 a 序列 [l,r]区间内的最大子段和，那么最终我们要求的答案就是 get(nums, 0, nums.size() - 1)。如何分治实现这个操作呢？
对于一个区间 [l,r]，我们取 m = (l+r)/2，相当于对区间 [l,m]和 [m+1,r]分治求解。当递归逐层深入直到区间长度缩小为 1 的时候，递归「开始回升」。这个时候我们考虑如何通过 [l,m]区间的信息和 [m+1,r] 区间的信息合并成区间 [l,r]的信息。最关键的两个问题是：
我们要维护区间的哪些信息呢？
我们如何合并这些信息呢？
对于一个区间 [l,r][l,r]，我们可以维护四个量：
ISum 表示 [l,r] 内以 l为左端点的最大子段和
rSum 表示 [l,r] 内以 r为右端点的最大子段和
mSum 表示 [l,r] 内的最大子段和
iSum 表示 [l,r]的区间和
以下简称 [l,m]为 [l,r]的「左子区间」，[m+1,r] 为 [l,r] 的「右子区间」。我们考虑如何维护这些量呢（如何通过左右子区间的信息合并得到 [l,r]的信息）？对于长度为 1的区间 [i, i]，四个量的值都和 nums[i] 相等。对于长度大于 1 的区间：
首先最好维护的是iSum，区间 [l,r] 的 iSum 就等于「左子区间」的 iSum 加上「右子区间」的 iSum。
对于 [l,r]的 lSum，存在两种可能，它要么等于「左子区间」的 lSum，要么等于「左子区间」的iSum 加上「右子区间」的lSum，二者取大。
对于 [l,r]的rSum，同理，它要么等于「右子区间」的rSum，要么等于「右子区间」的 \iSum 加上「左子区间」的rSum，二者取大
当计算好上面的三个量之后，就很好计算 [l,r] 的 mSum 了。我们可以考虑 [l,r] 的mSum 对应的区间是否跨越 m——它可能不跨越 m，也就是说 [l,r]的mSum 可能是「左子区间」的 mSum 和 「右子区间」的mSum 中的一个；它也可能跨越 m，可能是「左子区间」的 rSum 和 「右子区间」的 lSum 求和。三者取大。
代码如下
class Solution {
public:
struct Status {
int lSum, rSum, mSum, iSum;
};
Status pushUp(Status l, Status r) {
int iSum = l.iSum + r.iSum;
int lSum = max(l.lSum, l.iSum + r.lSum);
int rSum = max(r.rSum, r.iSum + l.rSum);
int mSum = max(max(l.mSum, r.mSum), l.rSum + r.lSum);
return (Status) {lSum, rSum, mSum, iSum};
};
Status get(vector<int> &a, int l, int r) {
if (l == r) {
return (Status) {a[l], a[l], a[l], a[l]};
}
int m = (l + r) >> 1;
Status lSub = get(a, l, m);
Status rSub = get(a, m + 1, r);
return pushUp(lSub, rSub);
}
int maxSubArray(vector<int>& nums) {
return get(nums, 0, nums.size() - 1).mSum;
}
};
分治法我有一些不是很懂这种思路，懵懵的，看完能理解，但还是懵，一句话总结，妙蛙种子吃了妙脆角到了米奇妙妙屋，妙到家了！
链接：最大子序和 - 最大子数组和 - 力扣（LeetCode） (leetcode-cn.com)