leetcode 689. Maximum Sum of 3 Non-Overlapping Subarrays

In a given array nums of positive integers, find three non-overlapping subarrays with maximum sum.
Each subarray will be of size k, and we want to maximize the sum of all 3*k entries.
Return the result as a list of indices representing the starting position of each interval (0-indexed). If there are multiple answers, return the lexicographically smallest one.
Example:
Input: [1,2,1,2,6,7,5,1], 2
Output: [0, 3, 5]
Explanation: Subarrays [1, 2], [2, 6], [7, 5] correspond to the starting indices [0, 3, 5].
We could have also taken [2, 1], but an answer of [1, 3, 5] would be lexicographically larger.

Three non-overlapping subarrays,
We can divide it into three intervals [0... I-1] [i... i +k-1] [i+k... ]
Enumeration from this interval [0... K-1] [k... 2k-1] [2k... ]

Calculate the value of the window with the largest size k from the left in advance, and the corresponding Index
From the right, the maximum size is the value of the window k, corresponding to the Index.
For enumerating the middle k-sized window, the complexity is O(N)

The subscript of this question is too confusing and easy to make mistakes. We must draw the interval.
Also note that when you come from the right, the max value is equal and you need to replace it (because we seek the smallest Index from the left).

public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
        int n = nums.length;
        int[] sums = new int[n+1];
        sums[0] = 0;
        for(int i = 0; i< nums.length;i++) {
            sums[i+1] = sums[i] + nums[i]; //Sums [i], the sum of all the numbers before i, excluding I
        } // The sum of windows with size k can also be obtained directly.
        int[] left = new int[n];  int[] right = new int[n];
        int max = Integer.MIN_VALUE;
        for(int i=0;i<nums.length-k;i++) {
            int cur = sums[i+k] - sums[i]; 
            if(cur > max) { //Bigger than sign, because no replacement is needed if equal.
                left[i] = i; //Left [i]: when the window with the size of K in the number before I + k is the largest, the starting index
                max = cur;
            } else {
                left[i] = left[i-1];
            }        
        }
        max = Integer.MIN_VALUE;
        for(int i = nums.length - k; i>=0;i--) {
            int cur = sums[i+k] - sums[i];
            if(cur >= max) { //Greater than or equal to sign, because equal need to be replaced
                right[i] = i; //Right [i]: When the window size k is the largest in the number after i, the start index
                max = cur;
            } else {
                right[i] = right[i+1];
            }  
        }
        
        int[] res = new int[3]; max = Integer.MIN_VALUE;
        for(int i=k; i<=nums.length-k*2;i++) {
            int l = left[i-k], r = right[i+k];
            int cur = sums[l+k] - sums[l] + sums[r+k] -sums[r] + sums[i+k] - sums[i];
            if(cur > max) {
                res[0] = l; res[1] = i; res[2] = r;
                max = cur;
            }
        }
        return res;
    }

Tags: Windows

Posted on Sun, 06 Oct 2019 22:16:42 -0700 by hendoyeah