【力扣题解】【53. 最大子数组和】通过很好理解的滑动窗口来解决这道题

53. 最大子数组和

总结和复盘

一年半以前，我居然以为这道题没办法使用滑动窗口来解决。
现在也搞不明白当时为什么会说找不到解。
所以后面采用了动态规划方法。
这是当时的注释。

class Solution {
public:// 刚看到这道题，我的想法是滑动窗口，因为这是数组，然后又是求一个连续部分// 为什么不能用滑动窗口呢？// 滑动窗口的时间复杂度不满足？// 滑动窗口，根据之前做的题，是先找到一个解，然后再去优化解// 但这道题，问题就在于你没办法首先就找到一个解// 动态规划：一般就是用来求最值int maxSubArray(vector<int>& nums) {if (nums.size() == 1)return nums[0];vector<int> dp(nums.size(), 0);dp[0] = nums[0];int max = nums[0];for (int i = 1; i < nums.size(); ++i) {dp[i] = std::max(dp[i-1] + nums[i], nums[i]);max = std::max(dp[i], max);}return max;}};

今天使用滑动窗口的方法重新做了一下这道题，也很好理解的。
主要是把负数的情况处理好。记住：L++，窗口是变小了，窗口内元素之后要减去nums[L]。

class Solution {
public:int maxSubArray(vector<int>& nums) {// 第一步：题目要求，子数组最少包含一个元素// 所以我们就设置，在初始时，窗口内只有一个元素，就是第一个元素int L = 0, R = 1;int sum = nums[L]; int answer = sum;// 第二步：如果没有负数的情况，就很简单了// 比如输入数组是：[1,2,3,4,5,6]// R不断增大，窗口不断增大// 最大子数组和，就是所有元素的和while (R < nums.size()) {// 最后看第三步(这个 while 循环)// 比如输入数组是：[-1,-2,-3,-4,-5,-6]// sum代表窗口内元素之和，如果R++扩大窗口搞不定了，则L++使窗口变小，// sum就要相应地减掉nums[L]。// 当窗口内无元素时，sum等于0，这个while不再满足，则又开始R++。while (sum < 0) {sum -= nums[L];L++;}sum += nums[R];// 窗口每一次变化，answer都已更新了// 所以不用操心增加 L 对结果的影响answer = std::max(answer, sum);R++;}return answer;}
};