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).
算法:假设i为要求的第2个subarray的起始点,则在[0, i - 1]和[i + k, end]各存在一个subarray,找出这3个subaaray和的最大值时的坐标就可
恶心的实现题,注意各种index的计算,最好用一个具体例子。
计算subarray的题一般都要用到累加数组,这题也不例外。
恶心的实现题,注意各种index的计算,最好用一个具体例子。
计算subarray的题一般都要用到累加数组,这题也不例外。
class Solution { public int[] maxSumOfThreeSubarrays(int[] nums, int k) { int n = nums.length; int[] rt = new int[3], sums = new int[n + 1], leftMax = new int[n], rightMax = new int[n]; // 计算累加数组 for (int i = 0; i < n; i++) { sums[i + 1] = sums[i] + nums[i]; } // 计算i左边的最大subarray和,DP for (int i = 1; i < n - 3 * k + 1; i++) { int cur = sums[i + k ] - sums[i]; int preMax = sums[leftMax[i - 1] + k] - sums[leftMax[i - 1]]; if (cur > preMax) { leftMax[i] = i; }else { leftMax[i] = leftMax[i - 1]; } } // 计算i右边的最大subarray和,DP rightMax[n - k] = n - k; for (int i = n - k - 1; i >= 2 * k; i--) { int cur = sums[i + k] - sums[i]; int preMax = sums[rightMax[i + 1] + k] - sums[rightMax[i + 1]]; if (cur > preMax) { rightMax[i] = i; }else { rightMax[i] = rightMax[i + 1]; } } int max = 0; for (int i = k; i <= n - 2 * k; i++) { int left = leftMax[i - k]; int right = rightMax[i + k]; int maxLeft = sums[left + k] - sums[left]; int maxRight = sums[right + k] - sums[right]; int cur = sums[i + k] - sums[i]; int total = maxLeft + maxRight + cur; if (total > max) { rt[0] = left; rt[1] = i; rt[2] = right; max = total; } } return rt; } }
No comments:
Post a Comment