算法:最大子数组和

这道题使用的是动态规划思想（Kadane算法），目标是在数组中找到一个连续子数组，使这个子数组元素之和最大。

算法从数组的第一个元素开始向后遍历，并维护两个变量：

一个变量表示“以当前元素结尾的连续子数组的最大和”。

另一个变量表示“遍历到目前为止出现过的最大连续子数组和”。

对于数组中的每一个元素，都要思考一个问题：

当前元素应该接到前面的连续子数组后面，还是自己重新开始形成一个新的连续子数组？

具体来说：

如果前面累计得到的和再加上当前元素，比当前元素本身还大，那么说明前面的部分对结果有贡献，应该继续保留，把当前元素接在后面。

如果前面累计得到的和再加上当前元素，还不如当前元素本身大，那么说明前面的部分已经成为负担，应该舍弃之前的连续子数组，从当前元素重新开始计算。

因此，每遍历到一个新元素时，都计算：

继续延伸之前的连续子数组得到的和；

从当前元素重新开始得到的和；

取两者中的较大值，作为“以当前元素结尾的最大连续子数组和”。

随后，再将这个结果与历史记录中的最大值进行比较：

如果当前得到的连续子数组和更大，就更新全局最大值；

否则保持原来的最大值不变。

整个过程只需要遍历数组一次。

从本质上看，这个算法利用了这样一个规律：

如果一个连续子数组的和已经变成负数，那么它只会拖累后面的结果，因此没有必要继留；

如果它是正数，则可以帮助后面的元素获得更大的和，因此应该保留。

最终，当遍历结束时，记录下来的全局最大值就是整个数组中的最大连续子数组和。

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; }