题目描述：
输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组，找到一个具有最大和的连续子数组。
1.子数组是连续的，比如[1,3,5,7,9]的子数组有[1,3]，[3,5,7]等等，但是[1,3,7]不是子数组
2.如果存在多个最大和的连续子数组，那么返回其中长度最长的，该题数据保证这个最长的只存在一个
3.该题定义的子数组的最小长度为1，不存在为空的子数组，即不存在[]是某个数组的子数组
4.返回的数组不计入空间复杂度计算
数据范围:
1<=n<=105
−100<=a[i]<=100
要求:时间复杂度O(n)，空间复杂度O(n)
进阶:时间复杂度O(n)，空间复杂度O(1)
示例：
输入：
[1,2,-3,4,-1,1,-3,2]
返回值：
[1,2,-3,4,-1,1]
说明：
经分析可知，最大子数组的和为4，有[4],[4,-1,1],[1,2,-3,4],[1,2,-3,4,-1,1]，故返回其中长度最长的[1,2,-3,4,-1,1]
解题思路：
本题考察算法-动态规划算法的使用。用两种动态规划的解法。
解法一：使用常规的动态规划思路：用一个vector-dp存储到各个下标时的最大连续子数组和，进行一轮遍历，若dp[i-1]+array[i]比array[i]大，说明到前一下标为止的最大连续子数组，可以把当前下标纳入到该连续子数组中；反之，则以array[i]为新的起点，继续向后扩展连续子数组；与此同时，动态刷新最大值maxsum。在上述过程中，注意还要刷新连续子数组的左右区间位置信息。
解法二：对空间复杂度进行优化：常规解法使用vector来记录各个下标的最大连续子数组和，但本题目的要求并没有需要读取vector中信息，因此该vector可以优化掉。用x代替dp[i-1]，相当于当前下标前的最大连续子数组和，其他的同解法一一致，这样vector的空间就节省下来了。在上述过程中，注意还要刷新连续子数组的左右区间位置信息。
测试代码：
解法一：动态规划
class Solution { public: vector<int> FindGreatestSumOfSubArray(vector<int>& array) { vector<int> res; // 记录到下标i为止的最大连续子数组和 vector<int> dp(array.size(), 0); dp[0]= array[0]; int maxsum = dp[0]; // 记录当前连续子数组的左右区间 int left = 0, right = 0; // 记录最大连续子数组的左右区间 int maxl = 0, maxr = 0; for (int i = 1; i < array.size(); i++) { right++; // 确定到当前下标为止时的连续子数组和最大值 dp[i] = max(dp[i - 1] + array[i], array[i]); // 若当前值本身超过已知最大连续子数组，则刷新左区间位置 if (dp[i - 1] + array[i] < array[i]){ left = right; } // 刷新最大值 // x如果比之前的最大值大，则刷新 // 一样大时，还要判断下左右区间的长度，取长度大的刷新 if (dp[i] > maxsum || (dp[i] == maxsum && (right - left + 1) > (maxr - maxl + 1))) { maxsum = dp[i] ; maxl = left; maxr = right; } } // 获取最大且最长的连续子数组 for (int i = maxl; i <= maxr; i++) res.push_back(array[i]); return res; } };
解法二：动态规划进阶
class Solution { public: vector<int> FindGreatestSumOfSubArray(vector<int>& array) { vector<int> res; // 记录到下标i为止的最大连续子数组和 int x = array[0]; int maxsum = x; // 记录当前连续子数组的左右区间 int left = 0, right = 0; // 记录最大连续子数组的左右区间 int maxl = 0, maxr = 0; for (int i = 1; i < array.size(); i++) { right++; // 确定到当前下标为止时的连续子数组和最大值 // 若当前值本身超过已知最大连续子数组，则刷新左区间位置 if (x + array[i] < array[i]){ left = right; x = array[i]; } else{ x = x + array[i]; } // 刷新最大值 // x如果比之前的最大值大，则刷新 // 一样大时，还要判断下左右区间的长度，取长度大的刷新 if (x > maxsum || (x == maxsum && (right - left + 1) > (maxr - maxl + 1))) { maxsum = x; maxl = left; maxr = right; } } // 获取最大且最长的连续子数组 for (int i = maxl; i <= maxr; i++) res.push_back(array[i]); return res; } };
