关于放弃运行求和方法的最大子数组问题

Question

查看Leetcode#53(最大子阵列，https://leetcode.com/problems/maximum-subarray/)，我在评论中看到了这个解决方案，并对我的代码进行了调整。但有一部分我不明白——有人能解释一下吗？

我希望用滑动窗口的方法来解决这个问题。

class Solution {
public:
int maxSubArray(vector<int>& nums) { // runtime O(n), space O(1)
int largestSum = nums[0];
int windowSum = 0;
// int windowStart = 0;

for (int windowEnd = 0; windowEnd < nums.size(); windowEnd++) {
windowSum += nums[windowEnd];

if (nums[windowEnd] > windowSum) { // if the value at this index is greater than the running sum up to and including this index, abandon the running sum and restart the sliding window from here.
windowSum = nums[windowEnd]; 
// windowStart = windowEnd; is essentially what we are doing
}

if (windowSum > largestSum) { // the window has at least 1 number
largestSum = windowSum;
}
}

return largestSum;
}
};

我很困惑，如果我们遇到一个单独的值大于运行总和的值，为什么我们放弃运行总和是有效的。有人能解释一下为什么这种方法对我有效吗？也许举一两个例子？不明白为什么这不跳过潜在的滑动窗口。

Answer 1

代码写得很差，在某种程度上掩盖了它的操作。在您询问的if条件中，唯一可能为真的方法是，在循环迭代开始之前，总和为负。这就是它真正重新启动的回应：一个总体上毫无帮助的前缀。