锐客网

  1. 首页 > 睿知 > it技术 > >

动态规划——Maximum Sum of 3 Non-Overlapping Subarrays

IT知识动态规划overlappingmaximum

登山则情满于山，观海则意溢于海。这篇文章主要讲述动态规划——Maximum Sum of 3 Non-Overlapping Subarrays相关的知识，希望能为你提供帮助。
这个题对我来说真的是相当难的题目了，严格来讲可能不算是个动态规划的题目，但这个题目对类似的划分多个非重叠连续子区间的问题提供了一个很好解决方案
【动态规划——Maximum Sum of 3 Non-Overlapping Subarrays】这个题目需要找三个非重叠的连续子区间，通过维护两个数组将第一个和第三个子区间可能的开始pos记录下来，在中间那个子区间开始的pos遍历时限制其边界范围，根据长度能恰到好处的将三个子区间划分成非重叠的，还使用了集合相减代替累加这样比较简单好用的技巧
下面提供代码：

1 class Solution { 2public int[] maxSumOfThreeSubarrays(int[] nums, int k) { 3int len = nums.length; 4int[]sum = new int[len+1]; 5for(int i = 0; i< len; i++) 6sum[i+1] = sum[i]+nums[i]; 7int[]posLeft = new int[len]; 8int[]posRight = new int[len]; 9posLeft[k-1] = 0; 10int total = sum[k]-sum[0]; 11for(int i = k; i< len; i++) { 12if(total< sum[i+1]-sum[i+1-k]) { 13total = sum[i+1]-sum[i+1-k]; 14posLeft[i] = i-k+1; 15}else posLeft[i] = posLeft[i-1]; 16} 17posRight[len-k] = len-k; 18total = sum[len]-sum[len-k]; 19for(int i = len-k-1; i> =0; i--) { 20if(total< sum[i+k]-sum[i]) { 21total = sum[i+k]-sum[i]; 22posRight[i]= i; 23}else posRight[i] = posRight[i+1]; 24} 25int l = 0,r = 0,max = 0; 26int[]arr = new int[3]; 27for(int i = k; i< =len-2*k; i++) { 28l = posLeft[i-1]; 29r = posRight[i+k]; 30total = (sum[l+k]-sum[l])+(sum[i+k]-sum[i])+(sum[r+k]-sum[r]); 31if(total> max) { 32arr[0] = l; arr[1] = i; arr[2] = r; 33max = total; 34} 35} 36return arr; 37} 38 }

 

    推荐阅读


    上一篇：投稿|迪士尼的内在增长，值得让人忽略外部问题

    下一篇：从零开始搭建架构实施Android项目