数据结构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结尾的子数组和最大值为

对于2，以b结尾的子数组和最大值为

对于3，以c结尾的子数组和最大值为

依次类推：

由公式1-5可得，数组{a, b, c, d, e}中连续子序列和最大值为

对于数组

，我们设

为以第

个元素结尾的连续子数组和最大值，则有：

其中

（n为数组元素的个数）。其连续子序列和最大值为

因此，此题代码实现如下：

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