数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法学C++中大小为K的M个不相交子数组的最大和
问题陈述
给定一个数组和两个数字M和K。我们需要找到数组中大小为K的M个最大子数组（不相交）的和。（数组顺序保持不变）。K是子数组的大小，M是子数组的个数。可以假设数组的大小大于m*k。如果数组总大小不是k的倍数，则我们可以取部分最后一个数组。
示例
如果给定数组为 = {2, 10, 7, 18, 5, 33, 0}，N = 7，M = 3，K = 1，则输出将为61，子集为：
{33, 18, 10}算法
- 我们创建一个前缀和数组，该数组的每个索引都包含给定数组中从“索引”到“索引+K”的所有元素的和。和数组的大小将为n+1-k
- 现在，如果我们包含大小为k的子数组，那么我们不能再次在任何其他子数组中包含该子数组的任何元素，因为它会创建重叠的子数组。因此，我们通过排除包含的子数组的k个元素来进行递归调用
- 如果我们排除一个子数组，那么我们可以在其他子数组中使用该子数组的接下来的k-1个元素，因此我们将通过只排除该子数组的第一个元素来进行递归调用。
- 最后返回最大值(包含的和, 排除的和)
示例
#include <bits/stdc++.h>
using namespace std;
void calculatePresumArray(int presum[], int arr[], int n, int k) {
for (int i = 0; i < k; i++) {
presum[0] += arr[i];
}
for (int i = 1; i <= n - k; i++) {
presum[i] += presum[i-1] + arr[i+k-1] - arr[i- 1];
}
}
int maxSumMnonOverlappingSubarray(int presum[], int m, int size, int k, int start) {
if (m == 0)
return 0;
if (start > size - 1)
return 0;
int mx = 0;
int includeMax = presum[start] + maxSumMnonOverlappingSubarray(presum, m - 1, size, k, start + k);
int excludeMax = maxSumMnonOverlappingSubarray(presum, m, size, k, start + 1);
return max(includeMax, excludeMax);
}
int main() {
int arr[] = { 2, 10, 7, 18, 5, 33, 0 };
int n = sizeof(arr)/sizeof(arr[0]);
int m = 3, k = 1;
int presum[n + 1 - k] = { 0 };
calculatePresumArray(presum, arr, n, k);
cout << "Maximum sum = " << maxSumMnonOverlappingSubarray(presum, m, n + 1 - k, k, 0) << endl;
return 0;
}编译并执行上述程序时，将生成以下输出：
输出
Maximum sum = 61
更新于：2019年12月20日
209 次浏览
广告