C++で指定された合計以下の合計を持つ最大合計サブ配列

この問題では、配列と合計が与えられます。私たちのタスクは、c++で指定された合計以下の合計を持つ最大合計サブ配列を見つけるプログラムを作成することです。

合計が指定された合計以下である、n以下の任意の長さのサブ配列を見つける必要があります。

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

入力 −配列={3、5、1、8、2、9}、合計=25

出力 − 25

説明 −合計が25以下のサブ配列は、{5、1、8、2、9}

最大合計サブ配列を見つける簡単な方法の1つは、配列を反復処理してすべてのサブ配列の合計を見つけてから、最も近いまたは等しい合計を見つけることです。ただし、この方法では2つのループが必要になるため、時間計算量はO（n * n）になります。

この問題を解決するためのより効率的な方法は、スライディングウィンドウを使用することです。 方法。ここでは、現在の合計を最大合計でチェックし、比較に基づいてウィンドウに要素を加算または減算します。

例

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

#include <iostream>
using namespace std;
int findMax(int a, int b){
   if(a>b)
      return a;
   return b;
}
int maxSumsubarray(int arr[], int n, int maxSum){
   int sum = arr[0], overallMax = 0, start = 0;
   for (int i = 1; i < n; i++) {
      if (sum <= maxSum)
      overallMax = findMax(overallMax, sum);
      while (sum + arr[i] > maxSum && start < i) {
         sum -= arr[start];
         start++;
      }
      sum += arr[i];
   }
   if (sum <= maxSum)
      overallMax = findMax(overallMax, sum);
   return overallMax;
}
int main(){
   int arr[] = {3, 1, 4, 7, 2, 9, 5};
   int n = sizeof(arr) / sizeof(arr[0]);
   int sum = 20;
   cout<<"The maximum sum of subarray with sum less than or equal to "<<sum<<" is "<<maxSumsubarray(arr, n, sum);
   return 0;
}

出力

The maximum sum of subarray with sum less than or equal to 20 is 18