相逢意气为君饮,系马高楼垂柳边。这篇文章主要讲述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).
The question asks for three non-overlapping intervals with maximum sum of all 3 intervals. If the middle interval is [i, i+k-1], where k < = i < = n-2k, the left interval has to be in subrange [0, i-1], and the right interval is from subrange [i+k, n-1].
So the following solution is based on DP.
posLeft[i] is the starting index for the left interval in range [0, i];
posRight[i] is the starting index for the right interval in range [i, n-1];
【689. Maximum Sum of 3 Non-Overlapping Subarrays】Then we test every possible starting index of middle interval, i.e. k < = i < = n-2k, and we can get the corresponding left and right max sum intervals easily from DP. And the run time is O(n).
Caution. In order to get lexicographical smallest order, when there are two intervals with equal max sum, always select the left most one. So in the code, the if condition is "> = tot" for right interval due to backward searching, and "> tot" for left interval.
class Solution { public int[] maxSumOfThreeSubarrays(int[] nums, int k) { int n = nums.length, maxsum = 0; int[] sum = new int[n+1], posLeft = new int[n], posRight = new int[n], ans = new int[3]; for (int i = 0; i < n; i++) sum[i+1] = sum[i]+nums[i]; // DP for starting index of the left max sum interval for (int i = k, tot = sum[k]-sum[0]; i < n; i++) { if (sum[i+1]-sum[i+1-k] > tot) { posLeft[i] = i+1-k; tot = sum[i+1]-sum[i+1-k]; } else posLeft[i] = posLeft[i-1]; } // DP for starting index of the right max sum interval // caution: the condition is "> = tot" for right interval, and "> tot" for left interval posRight[n-k] = n-k; for (int i = n-k-1, tot = sum[n]-sum[n-k]; i > = 0; i--) { if (sum[i+k]-sum[i] > = tot) { posRight[i] = i; tot = sum[i+k]-sum[i]; } else posRight[i] = posRight[i+1]; } // test all possible middle interval for (int i = k; i < = n-2*k; i++) { int l = posLeft[i-1], r = posRight[i+k]; int tot = (sum[i+k]-sum[i]) + (sum[l+k]-sum[l]) + (sum[r+k]-sum[r]); if (tot > maxsum) { maxsum = tot; ans[0] = l; ans[1] = i; ans[2] = r; } } return ans; } }
推荐阅读
- Android应用如何跳转到应用市场详情页面
- [学习笔记] CS131 Computer Vision: Foundations and Applications(Lecture 9 深度学习2)
- AndroidStudio自定义TODO
- 手机APP定制开发费用是多少
- fiddler 抓取 安卓模拟器 https包
- 猎豹手机降温神器怎样用?手机降温神器运用办法
- 3星gear solo价格多少钱?gear solo自动选择手表报价
- 高德地图小蜜覆盖全国多少个城市 高德小蜜覆盖的城市
- 电脑玩游戏卡怎样办?笔记本电脑玩游戏卡屏/卡顿处理办法