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

Question

查看 Leetcode #53（最大子数组，https://leetcode.com/problems/maximum-subarray/），我在评论中看到了这个解决方案并调整了我的代码。不过有一部分我不明白 — 谁能解释一下？

我想用滑动 window 方法解决它。

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;
    }
};

我很困惑为什么当我们遇到一个值单独大于 运行 总和时我们放弃 运行 总和。有人可以解释为什么这种方法对我有用吗？也许举一两个例子？不明白为什么这不会跳过潜在的滑动 windows。

Answer 1

代码写得不好，在某种程度上掩盖了它的操作。在您询问的 if 条件中，它可能为真的唯一方法是在循环迭代开始之前总和是否为 negative。这就是它真正重新启动以响应：一个整体无用的前缀。