BM72. [连续子数组的最大和]
https://www.nowcoder.com/exam/oj?tab=%E7%AE%97%E6%B3%95%E7%AF%87&topicId=295
BM72. 连续子数组的最大和
题目的主要信息：
- 输入一个长度为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;
}
};
复杂度分析：
- 时间复杂度：
- 空间复杂度：
，常数级变量，无额外空间
金山WPS公司福利 286人发布
我现在也只有一个保底
太难了