给定一个整数数组和一个整数 k,找出 k 个不重叠子数组使得它们的和最大。每个子数组的数字在数组中的位置应该是连续的。
int maxSubArray(vector<int> nums, int k) {
vector<vector<int>> dp(nums.size(), vector<int>(k + 1));
for (int i = 0; i < nums.size(); ++i) {
for (int j = 1; j <= k; ++j) {
if (i + 1 < j) {
continue;
}
if (i + 1 == j) {
if (i >= 1) {
dp[i][j] = nums[i] + dp[i - 1][j - 1];
} else {
dp[i][j] = nums[i];
}
continue;
}
dp[i][j] = dp[i - 1][j];
int sum = 0;
for (int w = i; w + 1 >= j; --w) {
sum += nums[w];
dp[i][j] = max(dp[i][j], sum + (w >= 1 ? dp[w - 1][j - 1] : 0));
}
}
}
return dp[nums.size() - 1][k];
}
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论