题目的主要信息:
- 输入一个长度为n的整型数组array,数组中的一个或连续多个整数组成一个子数组,找到一个具有最大和的连续子数组的和
- 不存在空数组,
- 基本要求:时间复杂度:,空间复杂度:
- 进阶要求:时间复杂度:,空间复杂度:
方法一:动态规划
具体做法:
可以用dp数组表示以下标i为终点的最大连续子数组和,则每次遇到一个新的数组元素,连续的子数组要么加上变得更大,要么它本身就更大,因此状态转移为,每次只要比较取最大值即可。
class Solution {
public:
int FindGreatestSumOfSubArray(vector<int> array) {
vector<int> dp(array.size(), 0); //记录到下标i为止的最大连续子数组和
dp[0] = array[0];
int maxsum = dp[0];
for(int i = 1; i < array.size(); i++){
dp[i] = max(dp[i - 1] + array[i], array[i]); //状态转移:连续子数组和最大值
maxsum = max(maxsum, dp[i]); //维护最大值
}
return maxsum;
}
};
复杂度分析:
- 时间复杂度:,一次遍历
- 空间复杂度:,动态规划辅助数组长度为
方法二:动态规划空间优化
具体做法:
方法一虽然时间复杂度达到了进阶要求,但是使用的空间。
我们注意到动态规划在状态转移的时候只用到了的信息,因此我们可以使用两个变量迭代来代替数组,状态转移的时候更新变量y,该轮循环结束的再更新x为y即可做到每次迭代都是上一轮的dp。
class Solution {
public:
int FindGreatestSumOfSubArray(vector<int> array) {
int x = array[0];
int y = 0;
int maxsum = x;
for(int i = 1; i < array.size(); i++){
y = max(x + array[i], array[i]); //状态转移:连续子数组和最大值
maxsum = max(maxsum, y); //维护最大值
x = y; //更新x的状态
}
return maxsum;
}
};
复杂度分析:
- 时间复杂度:,一次遍历
- 空间复杂度:,常数级变量,无额外空间