你的位置:首页 > Java教程

[Java教程]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.NoteThe subarray should contain at least one numberExampleGiven [-1,4,-2,3,-2,3],k=2, return 8Tags Expand 

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]+maxSubArrayindexrange(p,i-1)}, with p in the range j-1<=p<=i-1

 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     // write your code 9     if (nums.size() < k) return 0;10     int len = nums.size();11     12     int[][] dp = new int[len+1][k+1];13     14     for (int i=1; i<=len; i++) {15       for (int j=1; j<=k; j++) {16         if (i < j) {17           dp[i][j] = 0;18           continue;19         }20         dp[i][j] = Integer.MIN_VALUE;21         for (int p=j-1; p<=i-1; p++) {22           int local = nums.get(p);23           int global = local;24           for (int t=p+1; t<=i-1; t++) {25             local = Math.max(local+nums.get(t), nums.get(t));26             global = Math.max(local, global);27           }28           if (dp[i][j] < dp[p][j-1]+global) {29             dp[i][j] = dp[p][j-1]+global;30           }31         }32       }33     }34     return dp[len][k];35   }36 }

别人一个类似的方法,比我少一个loop,暂时没懂:

 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 }