编程题-最大子数组和（中等-重点【贪心、动态规划、分治思想的应用】）

题目：

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

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

解法一（枚举法-时间复杂度超限）：

暴力法，nums的数组元素被重复访问多次，导致时间复杂度超限，仅作为与下面两种方法的对比参考，并不是本题的正确解，时间复杂度为O(n^2)超限，如下为实现代码：

class Solution{
public:int maxSubArray(vector<int> &nums){//类似寻找最大最小值的题目，初始值一定要定义成理论上的最小最大值int max = INT_MIN;int numsSize = int(nums.size());for (int i = 0; i < numsSize; i++){        int sum = 0;for (int j = i; j < numsSize; j++){            sum += nums[j];if (sum > max){max = sum;}}}return max;}
};

解法二（动态规划）：

假设nums数组的长度是n，下标从0到n-1。我们用f(i)代表以第i个数结尾的【连续子数组的最大和】，很显然我们要求的答案就是：max(0≤i≤n-1){f(i)}。

因此我们只需要求出每个位置的f(i)，然后返回f数组中的最大值即可。那么我们如何求f(i)呢？我们可以考虑nums[i]单独成为一段还是加入f(i-1)对应的那一段，这取决于nums[i]和f(i-1)+nums[i]的大小，我们希望获得一个比较大的，于是可以写出动态规划转移方程：

于是我们可以只用一个变量pre来维护对于当前f(i)的f(i-1)的值是多少。

如果编号为 i 的子问题的结果是负数或者 0 ，那么编号为 i + 1 的子问题就可以把编号为 i 的子问题的结果舍弃掉，而子问题的定义必须以一个数结尾，因此如果子问题 i 的结果是负数或者 0，那么子问题 i + 1 的答案就是以 nums[i] 结尾的那个数。题目只要求返回结果，不要求得到最大的连续子数组是哪一个。这样的问题通常可以使用「动态规划或者贪心算法」解决。如下为实现代码：

class Solution {
public:int maxSubArray(vector<int>& nums) {//pre表示当前f(i)下的f(i-1)的值，初始时pre为0，//maxAns为截止至第i个索引元素时，最大的子数组和，最终的返回值int pre = 0, maxAns = nums[0];for (const auto &x: nums) {pre = max(pre + x, x);maxAns = max(maxAns, pre);}return maxAns;}
};

解法三（分治思想）：

我们定义一个操作get(a, l, r)表示查询a序列[l,r]区间内的最大子段和，那么最终要求的答案就是get(nums, 0, nums.size()-1)。如何分治实现这个操作呢？对于一个区间[l,r]，我们取，对区间[l,m]和[m+1,r]分治求解。当递归逐层深入直到长度缩小为1的时候，递归【开始回升】。这个时候我们考虑如何通过[l,m]区间的信息和[m+1,r]区间的信息合并成区间[l,r]的信息。最关键的两个问题是：

• 我们要维护区间的哪些信息呢？
• 我们如何合并这些信息呢？

对于一个区间 [l,r]，我们可以维护四个量：

• lSum 表示 [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 的区间：

1、首先最好维护的是 iSum，区间 [l,r] 的 iSum 就等于【左子区间】的 iSum 加上【右子区间】的 iSum。

2、对于[l,r]的lSum，存在两种可能，它要么等于【左子区间】的lSum，要么等于【左子区间】的lSum加上【右子区间的】lSum，二者取最大。

3、对于[l,r]的rSum，同理，它要么等于【右子区间】的rSum，要么等于【右子区间】的rSum加上【左子区间】的rSum加上右子区间的rSum。

4、当计算好上面的三个量之后，就很好计算[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;}
};

时间复杂度：假设我们把递归的过程看作是一颗二叉树的先序遍历，那么这颗二叉树的深度的渐进上界为 O(logn)，这里的总时间相当于遍历这颗二叉树的所有节点，故总时间的渐进上界是 ，故渐进时间复杂度为 O(n)。空间复杂度：递归会使用 O(logn) 的栈空间，故渐进空间复杂度为 O(logn)。

分治方法相比动态规划（方法二）的优势：它不仅可以解决区间 [0,n−1]，还可以用于解决任意的子区间 [l,r] 的问题。如果我们把 [0,n−1] 分治下去出现的所有子区间的信息都用堆式存储的方式记忆化下来，即建成一棵真正的树之后，我们就可以在 O(logn) 的时间内求到任意区间内的答案，我们甚至可以修改序列中的值，做一些简单的维护，之后仍然可以在 O(logn) 的时间内求到任意区间内的答案，对于大规模查询的情况下，这种方法的优势便体现了出来。这棵树就是上文提及的一种神奇的数据结构——线段树。

笔者小记：

1、动态规划与分治法和贪心法类似，都是将问题分解为更小的子问题，并通过求解子问题来得到全局最优解。然而，它们在处理子问题的方式上有所不同：

• 贪心法‌：当前选择依赖于已经作出的所有选择，但不依赖于有待于做出的选择和子问题。它自顶向下，一步一步地作出贪心选择。
• ‌分治法‌：各个子问题是独立的，一旦递归地求出各子问题的解后，自下而上地将子问题的解合并成问题的解。
• ‌动态规划‌：允许子问题不独立，通过自身子问题的解作出选择，对每一个子问题只解一次，并将结果保存起来，避免每次碰到时都要重复计算‌。

解决问题的时候，应根据题目要求划分采用贪心思想、动态规划思想、分治思想三类思想的哪类问题，再进行代码的实现，三种思想时间复杂度都较低，单层循环逻辑可实现。