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.

Note:

• nums.length will be between 1 and 20000.
• nums[i] will be between 1 and 65535.
• k will be between 1 and floor(nums.length / 3).

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56

class Solution { vector<int> sums; vector<int> nums; //compute the sum of [i, i+k-1] int sumInterval(int i, int k){ return sums[i+k-1]-(i-1>=0?sums[i-1]:0); } public: vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) { vector<int> ret(3); // if(k==0) return ret; int n = nums.size(), sum=0; vector<int> left(n, 0);//left[i] is the starting index of the max-sum interval ends before or at i vector<int> right(n, n-1);//right[i] is the starting index of the max-sum interval begins after or at i this->nums = nums; sums = nums; for(int i=1; i<n; i++) sums[i] += sums[i-1]; //ending index of "left" must be between [0...k-2] and [n-2k...n-1] //so the ending index of "left" must be in [k-1..n-2k-1] for(int i=k-1; i<n-2*k; ++i){ int tmp = sumInterval(i-k+1, k);//[i-k+1, i] if(tmp>sum){ sum = tmp; left[i] = i-k+1; }else{ left[i] = left[i-1]; } } sum = 0; //starting index of "right" must be between [0..2k-1] and [n-k+1..n-1] //so the starting index of "right" must be in [2k..n-k] for(int i=n-k; i>=2*k; --i){ int tmp = sumInterval(i, k);//sum of [i, i+k-1] if(tmp>=sum){ sum = tmp; right[i] = i; }else{ right[i] = right[i+1]; } } sum = 0; //starting index of middle interval must be in [k,n-2k] for(int i=k; i<=n-2*k; ++i){ int l = left[i-1], r = right[i+k]; int tmp = sumInterval(l, k) + sumInterval(i, k) + sumInterval(r, k); if(tmp>sum){ sum = tmp; ret[0]=l; ret[1]=i, ret[2]=r; } } return ret; } };