C++에서 주어진 크기의 겹치지 않는 두 하위 배열의 최대 합

이 문제에서는 양의 정수 배열과 숫자 k가 제공됩니다. 우리의 임무는 주어진 크기(k)의 겹치지 않는 두 하위 배열의 최대 합을 찾는 프로그램을 만드는 것입니다.

따라서 기본적으로 최대 합계가 있고 크기가 k인 두 개의 겹치지 않는(고유한) 하위 배열이 두 개 인쇄됩니다.

문제를 이해하기 위해 예를 들어보겠습니다.

입력 -

array = {7, 1, 6, 9, 2} , k = 2

출력 -

{7, 1} , {6, 9}

설명 -

all subarrays of size 2.
{7, 1} : sum = 7+1 = 8
{1, 6} : sum = 1+6 = 7
{6, 9} : sum = 6+9 = 15
{9, 2} : sum = 9+2 = 11
Two non-overlapping subarrays with max sums are {7,1} and {6,9}

이 문제를 해결하려면 모든 하위 배열과 그 합을 찾은 다음 서로 겹치지 않는 두 개의 최대 하위 배열을 확인하는 것이 간단한 솔루션입니다.

문제를 해결하는 효과적인 방법은 배열의 요소까지 모든 요소의 합계를 저장하는 접두사 합계 배열을 사용하는 것입니다. 그리고 k개의 요소를 검사하여 최대 합을 가진 부분배열을 찾습니다.

예시

솔루션 구현을 보여주는 프로그램,

#include <bits/stdc++.h>
using namespace std;
int findSubArraySum(int sum[], int i, int j){
   if (i == 0)
      return sum[j];
   else
      return (sum[j] - sum[i - 1]);
}
void maxSubarray(int arr[],int N, int K){
   int prefixsum[N];
   prefixsum[0] = arr[0];
   for (int i = 1; i < N; i++)
   prefixsum[i] = prefixsum[i - 1] + arr[i];
   pair<int, int> resIndex = make_pair(N - 2 * K, N - K);
   int maxSubarraySum = findSubArraySum(prefixsum, N - 2 * K, N - K - 1) + findSubArraySum(prefixsum, N - K, N - 1);
   pair<int, int> secondSubarrayMax = make_pair(N - K, findSubArraySum(prefixsum, N - K, N - 1));
   for (int i = N - 2 * K - 1; i >= 0; i--){
      int cur = findSubArraySum(prefixsum, i + K, i + 2 * K - 1);
      if (cur >= secondSubarrayMax.second)
         secondSubarrayMax = make_pair(i + K, cur);
      cur = findSubArraySum(prefixsum, i, i + K - 1) + secondSubarrayMax.second;
      if (cur >= maxSubarraySum){
         maxSubarraySum = cur;
         resIndex = make_pair(i, secondSubarrayMax.first);
      }
   }
   cout<<"{ ";
   for (int i = resIndex.first; i <resIndex.first + K; i++)
      cout<<arr[i]<<" ";
   cout<<"}"<<endl<<"{ ";
   for (int i = resIndex.second; i < resIndex.second + K; i++)
      cout<<arr[i]<<" ";
   cout<<"}"<<endl;
}
int main(){
   int arr[] = {2, 5, 1, 2, 7, 3, 0};
   int N = sizeof(arr) / sizeof(int);
   int K = 2;
   cout<<"Two non-overlapping subarrays with maximum sum are \n";
   maxSubarray(arr, N, K);
   return 0;
}

출력

Two non-overlapping subarrays with maximum sum are
{ 2 5 }
{ 7 3 }