题目链接
题目描述
给你一个整数数组 nums
,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
子数组 是数组中的一个连续部分。
题目分析
这道题我一开始想的是用双指针实现(实际上也是贪心的本质)。因为负数可能会对整个子数组具有负贡献,所以我们每次在sum
中加入一个数nums[i]
之后都要进行比较,如果sum
甚至比nums[i]
还要小的话,说明还不如直接从nums[i]
开始记录。所以我的代码是:
class Solution {
public:int maxSubArray(vector<int>& nums) {// 连续的最大和子数组,滑动窗口也许可以一试int i = 0; // i指向滑动窗口首端int sum = nums[i]; // 记录子数组的和int max_sum = sum; // 记录最大和int j = i+1; // j指向滑动窗口末尾while(j < nums.size()) {if(nums[j] + sum < nums[j]) { // 如果加入nums[j]是负贡献i = j; // 则重置滑动窗口首端进行记录j = i + 1;sum = nums[i];}else sum += nums[j++]; // 正贡献if(sum > max_sum) max_sum = sum;}return max_sum;}
};
上面的代码一开始判断负贡献那里我写的是nums[j] + sum < 0
,但实际上也没有考虑完全,这只是负贡献的一种。
不过实际上用不着双指针,只用一个i
和sum
就能完成:
class Solution {
public:int maxSubArray(vector<int>& nums) {int result = INT32_MIN;int count = 0;for (int i = 0; i < nums.size(); i++) {count += nums[i];if (count > result) { // 取区间累计的最大值(相当于不断确定最大子序终止位置)result = count;}if (count <= 0) count = 0; // 相当于重置最大子序起始位置,因为遇到负数一定是拉低总和}return result;}
};