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.
Given [-1,4,-2,3,-2,3], k=2, return 8
http://www.lintcode.com/en/problem/maximum-subarray-iii/
Discussion
dp[i][j]表示从前i个数( i.e., [0, i-1]) 中取j个subarray得到的最大值，那么要求的结果就是dp[n][k]：从前n个数中取k个subarray得到的最大和。
状态转移：从前i个中取j个，那么我们可以从前p个数（i.e., [0, p-1]）中取j-1个subarray，再加上从P到i-1这个subarray中的最大和（也就是Maximum Subarray问题）。从这句话里我们也可以读出来p的范围应该是j-1~i-1
//O(k*n^3) rum time
//O(k*n) space
class Solution {
public:
/**
* @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
*/
int maxSubArray(vector<int> nums, int k) {
if(nums.empty()) return 0;
int n = nums.size();
if(n < k) return 0;
vector<vector<int> > max_sum(n+1, vector<int>(k+1, INT_MIN));
//max_sum[i][j]: max sum of j subarrays generated from nums[0] ~ nums[i-1]
//note that j is always <= i
//init
for(int i=0; i<=n; i++) {
max_sum[i][0] = 0;
}
for(int i=1; i<=n; i++) {
for(int j=1; j<=min(i,k); j++) {
max_sum[i][j] = max_sum[i - 1][j];
//max_sum[i][j] equals to 1) max sum of j-1 subarrays generated from nums[0] ~ nums[p-1]
//plus 2) max sum of the subarry from nums[p] ~ nums[i-1]
//p can be j-1 ~ i-1
for(int p = i-1; p >= j-1; p--) {
//compute the max of of the subarry from nums[p] ~ nums[i-1]
int global = maxSubArray(nums, p, i-1);
max_sum[i][j] = max(max_sum[i][j], max_sum[p][j-1] + global);
}
}
}
return max_sum[n][k];
}
//compute max sum of subarray [start, end]
int maxSubArray(vector<int> &nums, int start, int end) {
int local = 0;
int global = INT_MIN;
for(int i=start; i<=end; i++) {
local = max(nums[i], local + nums[i]);
global = max(global, local);
}
return global;
}
};
Follow up
上面的算法是O(k*n^3)的复杂度，因为最里层求subarray的max sum也要耗费O(n). for(int p = i-1; p >= j-1; p--)和里面调用maxSubarry有重复计算的部分，p是从i-1往前加，这样的话直接update global就行了，就像在maxSubArray函数里那样。
class Solution {
public:
/**
* @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
*/
int maxSubArray(vector<int> nums, int k) {
if(nums.empty()) return 0;
int n = nums.size();
if(n < k) return 0;
vector<vector<int> > max_sum(n+1, vector<int>(k+1, INT_MIN));
//max_sum[i][j]: max sum of j subarrays generated from nums[0] ~ nums[i-1]
//note that j is always <= i
//init
for(int i=0; i<=n; i++) {
max_sum[i][0] = 0;
}
for(int i=1; i<=n; i++) {
for(int j=1; j<=min(i,k); j++) {
max_sum[i][j] = max_sum[i - 1][j];
//max_sum[i][j] equals to 1) max sum of j-1 subarrays generated from nums[0] ~ nums[p-1]
//plus 2) max sum of the subarry from nums[p] ~ nums[i-1]
//p can be j-1 ~ i-1
int global = INT_MIN;
int local = 0;
for(int p = i-1; p >= j-1; p--) {
//compute the max of of the subarry from nums[p] ~ nums[i-1]
global = max(max_sum_p, local+nums[p]);//这里要先用之前的local加上现在的nums[p]来update global，之后再update local
local = max(0, local+nums[p]);
max_sum[i][j] = max(max_sum[i][j], max_sum[p][j-1] + global);
}
}
}
return max_sum[n][k];
}
};