LeetCode [689] Maximum Sum of 3 Non-Overlapping Subarrays

 689. Maximum Sum of 3 Non-Overlapping Subarrays

Hard

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 57 58 59 60 61 62 63 64 65 66 67 68 69

class Solution { int getSum(int[] ps, int endIndex, int k){ return ps[endIndex+1] - ps[endIndex-k+1]; } public int[] maxSumOfThreeSubarrays(int[] nums, int k) { int n = nums.length; int[] ps = new int[n+1]; for(int i=1; i<=n; ++i){ ps[i] = ps[i-1] + nums[i-1]; } //nums[dp1[i]-k+1..dp1[i]] is the max subarr in nums[0..dp1[i]] int[] dp1 = new int[n]; for(int i=0; i<n; ++i){ if(i<k){ dp1[i] = i; }else{ if(getSum(ps, dp1[i-1], k)<getSum(ps, i, k)){ dp1[i] = i; }else{ dp1[i] = dp1[i-1]; } } } //dp2[i][0] is the first ending index; dp2[i][1] is the second ending index int[][] dp2 = new int[n][2]; for(int i=0; i<n; ++i){ if(i==2*k-1){ dp2[i][0] = k-1; dp2[i][1] = 2*k-1; }else if(i>=2*k){ if(getSum(ps, i, k)+getSum(ps, dp1[i-k], k)>getSum(ps, dp2[i-1][0], k)+getSum(ps, dp2[i-1][1], k)){ dp2[i][0] = dp1[i-k]; dp2[i][1] = i; }else{ dp2[i][0] = dp2[i-1][0]; dp2[i][1] = dp2[i-1][1]; } } } int[][] dp3 = new int[n][3]; for(int i=0; i<n; ++i){ if(i==3*k-1){ dp3[i][0] = k-1; dp3[i][1] = 2*k-1; dp3[i][2] = 3*k-1; }else if(i>=3*k){ int tmp = getSum(ps, i, k) + getSum(ps, dp2[i-k][0], k) + getSum(ps, dp2[i-k][1], k); int loc = getSum(ps, dp3[i-1][0], k) + getSum(ps, dp3[i-1][1], k) + getSum(ps, dp3[i-1][2], k); if(tmp>loc){ dp3[i][2] = i; dp3[i][1] = dp2[i-k][1]; dp3[i][0] = dp2[i-k][0]; }else{ dp3[i][2] = dp3[i-1][2]; dp3[i][1] = dp3[i-1][1]; dp3[i][0] = dp3[i-1][0]; } } } dp3[n-1][0] -= k-1; dp3[n-1][1] -= k-1; dp3[n-1][2] -= k-1; return dp3[n-1]; } }