C ++中M个大小为K的非重叠子数组的最大和
问题陈述
给定一个数组以及两个数字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}算法
我们创建一个presum数组，该数组在每个索引中包含给定数组中从'index'到'index+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