【贪心算法题记录】53. 最大子数组和
题目链接
题目描述
给你一个整数数组 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;}
};