C ++でサイズkのサブアレイの最大（または最小）合計を求めます

この問題では、配列arr[]と数kが与えられます。私たちのタスクは、サイズkのサブアレイの最大（または最小）合計を見つけることです。

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

入力： arr [] ={55、43、12、76、89、25、99}、k =2

出力： 165

説明：

サイズ2のサブアレイの合計は=76+ 89 =165

ソリューションアプローチ

この問題を解決する簡単な方法は、kサイズのサブ配列をすべて見つけて、最大値の合計を返すことです。

別のアプローチ スライディングウィンドウを使用しています kサイズのサブアレイの合計が見つかります。このために、次のkサイズのサブ配列では、最後のインデックス要素を減算し、次のインデックス要素を追加します。

次に、最大値を持つサブ配列の合計を返します。

ソリューションの動作を説明するプログラム

例

#include <iostream>
using namespace std;

int findMaxSumSubarray(int arr[], int n, int k) {
   
   if (n < k) {
      cout << "Invalid";
      return -1;
   }

   int maxSum = 0;
   for (int i=0; i<k; i++)
      maxSum += arr[i];
   int curr_sum = maxSum;
   for (int i=k; i<n; i++) {
      curr_sum += arr[i] - arr[i-k];
      maxSum = max(maxSum, curr_sum);
   }
   return maxSum;
}

int main() {
   
   int arr[] = {55, 43, 12, 76, 89, 25, 99};
   int n = sizeof(arr)/sizeof(arr[0]);
   int k = 2;
   cout<<"The sum of subarray with max sum of size "<<k<<" is "<<findMaxSumSubarray(arr, n, k);
   return 0;
}

出力

The sum of subarray with max sum of size 2 is 165