LeetCode--689_Maximum_Sum_of_3_NonOverlapping_Subarrays

眼前多少难甘事，自古男儿当自强。这篇文章主要讲述LeetCode--689_Maximum_Sum_of_3_NonOverlapping_Subarrays相关的知识，希望能为你提供帮助。
原题链接：点击这里
一道很水很水的背包问题？大概算不上背包吧QAQ 自己的dp 真的是太差劲啦，以后每天一道LeetCode 备战秋招！

package leetcode; public class a689_Maximum_Sum_of_3_NonOverlapping_Subarrays {public static int[] maxSumOfThreeSubarrays(int[] nums, int k) { int [] ans = new int [3]; int [][] dp = new int [3][nums.length+1]; int [] sum = new int [nums.length+1]; for(int j=1; j< =nums.length; j++) { if(j==1) { sum[j]=nums[j-1]; }else { sum[j]+=sum[j-1]+nums[j-1]; } } int mmx =0; for(int j=0; j< 3; j++) { int max = 0; for(int i = k*j+1; i< =nums.length-k+1; i++) { if(j==0) { dp[0][i] = sum[i+k-1]-sum[i-1]; }else { max = Math.max(max, dp[j-1][i-k]); dp[j][i] = max+sum[i+k-1]-sum[i-1]; mmx = Math.max(mmx, dp[j][i]); } } }for(int j=2; j> =0; j--) { for(int i=1; i< =nums.length-k+1; i++) { if(dp[j][i]==mmx) { ans[j]=i-1; mmx -= sum[i+k-1]-sum[i-1]; break; } } } return ans; }public static void main(String[] args) {int [] nums = {1,2,1,2,6,7,5,1}; int k = 2; maxSumOfThreeSubarrays(nums,k); }}

Runtime: 4 ms, faster than 82.08% of java online submissions for Maximum Sum of 3 Non-Overlapping Subarrays.

Memory Usage: 42.6 MB, less than 34.91% of Java online submissions forMaximum Sum of 3 Non-Overlapping Subarrays.

【LeetCode--689_Maximum_Sum_of_3_NonOverlapping_Subarrays】