leetcode-最大子序和

点击:题目链接:给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

思路

由题意可知,若连续的数组内,和的值变小,我们就需要重新开始计数。

所以我们可以推出这样一个递推关系,当第i个元素,当前的它的和的最大值取决于时候前面已知的和加上它是否变小,
若变小,则从当前元素重新计数,即当前的和为f(i) = num[i],
若变大,则当前和为f(i-1)+num[i]

式子可以变为: f(i) = max(num[i], f(i-1)+num[i])

拓展:由于我们只需要f(i-1),为节省空间(不使用哈希表),我们可以利用滚动数组,将f(i-1)表示为一个变量

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int max_val = nums[0];
int pre_sum = nums[0];

for(int i=1; i<nums.size(); ++i){
pre_sum = max(nums[i], (pre_sum+nums[i]));
max_val = max(pre_sum, max_val);
}

return max_val;
}
};

复杂度

时间:O(N), 空间O(1)

作者

Dylan Zhu

发布于

2021-04-09

更新于

2021-04-09

许可协议

评论

:D 一言句子获取中...