Looking at Leetcode #53 (Maximum Subarray, https://leetcode.com/problems/maximum-subarray/), I saw this solution in the comments and adapted my code to it. There is one part I don't understand though — can someone explain?

I am looking to solve it with the sliding window approach.

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

I'm confused as to why it works that we abandon the running sum if we come across a value that standing alone is greater than the running sum. Can someone explain why this approach works to me? Maybe with an example or two? Failing to see why this doesn't skip potential sliding windows.

CodePudding user response：

The code is poorly written, in a way which obscures its operation. In the if-condition you’re asking about, the only way it could be true is if the sum were negative before the beginning of the loop iteration. That’s what it’s really restarting in response to: an overall unhelpful prefix.