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이면 부분 집합이 -

{33, 18, 10}

알고리즘

• 주어진 배열의 '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