首页 > 代码库 > LintCode-Maximum Subarray III
LintCode-Maximum Subarray III
Given an array of integers and a number k, find k non-overlapping subarrays which have the largest sum.
The number in each subarray should be contiguous.
Return the largest sum.
Note
The subarray should contain at least one number
Analysis:
DP. d[i][j] means the maximum sum we can get by selecting j subarrays from the first i elements.
d[i][j] = max{d[p][j-1]+maxSubArray(p+1,i)}
we iterate p from i-1 to j-1, so we can record the max subarray we get at current p, this value can be used to calculate the max subarray from p-1 to i when p becomes p-1.
Solution:
1 public class Solution { 2 /** 3 * @param nums: A list of integers 4 * @param k: An integer denote to find k non-overlapping subarrays 5 * @return: An integer denote the sum of max k non-overlapping subarrays 6 */ 7 public int maxSubArray(ArrayList<Integer> nums, int k) { 8 if (nums.size()<k) return 0; 9 int len = nums.size();10 //d[i][j]: select j subarrays from the first i elements, the max sum we can get.11 int[][] d = new int[len+1][k+1];12 for (int i=0;i<=len;i++) d[i][0] = 0; 13 14 for (int j=1;j<=k;j++)15 for (int i=j;i<=len;i++){16 d[i][j] = Integer.MIN_VALUE;17 //Initial value of endMax and max should be taken care very very carefully.18 int endMax = 0;19 int max = Integer.MIN_VALUE; 20 for (int p=i-1;p>=j-1;p--){21 endMax = Math.max(nums.get(p), endMax+nums.get(p));22 max = Math.max(endMax,max);23 if (d[i][j]<d[p][j-1]+max)24 d[i][j] = d[p][j-1]+max; 25 }26 }27 28 return d[len][k];29 30 31 }32 }
Solution 2:
Use one dimension array.
1 public class Solution { 2 /** 3 * @param nums: A list of integers 4 * @param k: An integer denote to find k non-overlapping subarrays 5 * @return: An integer denote the sum of max k non-overlapping subarrays 6 */ 7 public int maxSubArray(ArrayList<Integer> nums, int k) { 8 if (nums.size()<k) return 0; 9 int len = nums.size();10 //d[i][j]: select j subarrays from the first i elements, the max sum we can get.11 int[] d = new int[len+1];12 for (int i=0;i<=len;i++) d[i] = 0; 13 14 for (int j=1;j<=k;j++)15 for (int i=len;i>=j;i--){16 d[i] = Integer.MIN_VALUE;17 int endMax = 0;18 int max = Integer.MIN_VALUE; 19 for (int p=i-1;p>=j-1;p--){20 endMax = Math.max(nums.get(p), endMax+nums.get(p));21 max = Math.max(endMax,max);22 if (d[i]<d[p]+max)23 d[i] = d[p]+max; 24 }25 }26 27 return d[len];28 29 30 }31 }
LintCode-Maximum Subarray III
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。