lintcode 最大子数组III-白红宇

v题目描述

　　给定一个整数数组和一个整数 k，找出 k 个不重叠子数组使得它们的和最大。每个子数组的数字在数组中的位置应该是连续的。

　　返回最大的和。

v注意事项

　　子数组最少包含一个数

v样例

　　给出数组 [-1,4,-2,3,-2,3] 以及 k = 2，返回 8

v思路

　　dp[i][j] = max(dp[x][j-1]+maxs[x+1][i])

　　dp[i][j] 表示前 i 个数中 j 个子数组的最大值，

　　maxs[i][j] 表示第i个数到第j个数中最大子数组的和。

v代码

                            
public
class
Solution { 
    
/**
     
* @param nums: A list of integers
     
* @param k: An integer denote to find k non-overlapping subarrays
     
* @return: An integer denote the sum of max k non-overlapping subarrays
     
*/
    
public
int
maxSubArray(
int
[] nums, 
int
k) { 
        
// write your code here
        
int
[][] maxs = 
new
int
[nums.length][nums.length];
        
int
[][] dp = 
new
int
[nums.length][k+
1
];
        
for
(
int
i=
0
; i<nums.length; ++i) { 
            
for
(
int
j=i; j<nums.length; ++j) { 
                
maxs[i][j] = maxSum(nums, i, j);
            
}
        
}
        
        
for
(
int
i=
0
; i<dp.length; ++i) { 
            
for
(
int
j=
0
; j<dp[i].length; ++j) { 
                
dp[i][j] = Integer.MIN_VALUE;
            
}
        
}
        
for
(
int
i=
0
; i<dp.length; ++i) { 
            
dp[i][
1
] = maxs[
0
][i];
        
}
        
for
(
int
i=
1
; i<nums.length; ++i) { 
            
for
(
int
j=
2
; j<=k; ++j) { 
                
for
(
int
x=j-
2
; x<i; ++x) { 
                    
dp[i][j] = Math.max(dp[i][j], dp[x][j-
1
] + maxs[x+
1
][i]);
                
}
            
}
        
}
        
return
dp[nums.length-
1
][k];
    
}
    
private
int
maxSum(
int
[] nums, 
int
i, 
int
j) { 
        
int
sum = 
0
, maxs = Integer.MIN_VALUE;
        
for
(
int
x = i; x <= j; ++x) { 
            
sum += nums[x];
            
if
(maxs < sum) { 
                
maxs = sum;
            
}
            
if
(sum < 
0
) { 
                
sum = 
0
;
            
}
        
}
        
return
maxs;
    
}
}
         
       

本文转自小眼儿博客园博客，原文链接：http://www.cnblogs.com/hujunzheng/p/7376237.html，如需转载请自行联系原作者