C++で指定されたサイズの重複しない2つのサブ配列の最大合計

この問題では、正の整数の配列と数kが与えられます。私たちのタスクは、指定されたサイズ（k）の2つの重複しないサブ配列の最大合計を見つけるプログラムを作成することです。

したがって、基本的に、合計が最大でサイズがkの2つの重複しない（別個の）サブ配列を2つ印刷します。

問題を理解するために例を見てみましょう

入力 −

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}

この問題を解決するための簡単な解決策は、すべてのサブアレイとそれらの合計を見つけてから、互いに重複しない2つの最大サブアレイをチェックすることです。

問題を解決するための効果的なアプローチは、配列の要素まですべての要素の合計を格納するプレフィックス合計配列を使用することです。そして、サブアレイの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 }