C++ sliding window solution


  • 1
    A

    Evaluate the sum in the window [i,j]:

    • Initialize i=j=0;
    • Increase window size from the right one-by-one, while keeping track of the sum A[i]..A[j]. As long as the sum is positive, we want that window to be included in the final solution.
    • As soon as the sum is negative, including that window will hurt rather than help the final solution. So make i=j (window size zero), and start over again.
    • Keep in mind that a window might have had its maximum sum occur somewhere in the middle, but since we have to be contiguous, we keep increasing it beyond that point too. The only moment you have to break is when its sum is negative, in which case you might as well start with a fresh window.
    • max is the maximum sum calculated at any point during all of this.

    i and j always move forward, so they only make one pass over the array: O(n) time, constant space.

    class Solution {
    public:
       int maxSubArray(vector<int>& nums) {
    	int max = INT_MIN;
    	int N = nums.size();
    	//[i,j] sliding window
    	int i=0; int j=0;
    	while (i<N) {
    		int sum = 0;
    		while (j<N) {
    			sum += nums[j];
    			if (sum>max) max = sum;
    			if (nums[j]>sum) break;
    			else j++;
    		}
    		i = j;
    	}
    	return max;
       }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.