JZ85 连续子数组的最大和（二）
描述
输入一个长度为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)$
示例略
题解
仔细看了一下，这道题和JZ42还不一样，JZ42只需要返回最大值即可，这道题需要返回最长的最大子数组本身。
首先我们还是定义最小子问题，我们要找的目标是一样的，仍然是具有最大和的连续子数组，这次我们则可以定义一个二维数组$dp$，然后在其中储存数对，用来表示以i结尾的最长的最大子数组。
到这里我想到并不需要二维数组，只需要一维数组$indexDp$即可，其中保存的是以i为结尾拥有最大和的子数组的开头即可，这样再维护一个数组用来表示这个子数组的和就可以了。
这道题提到了可能存在多个有着相同的最大和的最大子数组，需要返回一个最长的，我们只需要在最后再次遍历一遍$dp$，寻找最大值的同时，将相应的$i-index+1$长度比较一下就可以了。
最后寻找最长最大的时候的边界条件写了很久，这道题的优化和JZ42的空间$O(1)$优化一样，$dp$都只依赖于它的前一项，所以只需要做一个$pre$来进行迭代就可以了。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| #include <algorithm>
#include <vector>
class Solution {
public:
vector<int> FindGreatestSumOfSubArray(vector<int>& array) {
vector<int> dp;
vector<int> indexDp;
dp.push_back(array[0]);
indexDp.push_back(0);
for (int i = 1; i < array.size(); i++) {
if (array[i] > dp[i - 1] + array[i]) {
dp.push_back(array[i]);
indexDp.push_back(i);
} else {
dp.push_back(dp[i - 1] + array[i]);
indexDp.push_back(indexDp[i - 1]);
}
}
int maxSum = -101;
int maxLength = -1;
int start = 0;
int end = 0;
for (int i = 0; i < dp.size(); i++) {
cout << dp[i] << " " << maxSum << " " << indexDp[i] << " " << maxLength << endl;
if (dp[i] > maxSum || (dp[i] == maxSum && (i - indexDp[i] + 1) > maxLength)) {
maxSum = dp[i];
maxLength = i - indexDp[i] + 1;
start = indexDp[i];
end = i;
}
}
vector<int> ans;
for (int i = start; i <= end; i++)
ans.push_back(array[i]);
return ans;
}
};
|
