最大サブアレイサイズ。C++プログラムでは、そのサイズのすべてのサブアレイの合計がk未満になります。

この問題では、n個の正の整数と整数kで構成される配列arr[]が与えられます。私たちのタスクは、Maximumsubarrayサイズを見つけるプログラムを作成して、そのサイズのすべてのサブアレイの合計がk未満になるようにすることです。

問題の説明 −配列の要素からサイズで作成されたすべてのサブ配列が、k以下の要素の合計を持つように、サブ配列の最大サイズを見つける必要があります。

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

入力

arr[n] = {4, 1, 3, 2}, k = 9

出力

3

説明

サイズ3のすべてのサブアレイとそれらの合計-

{4, 1, 3} = 8
{1, 3, 2} = 6
The sum of all subarrays of size 3 is less than or equal to k.

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

この問題の簡単な解決策は、サイズがkより大きいサブアレイを見つけることです。このために、指定されたインデックスまでの要素の合計を示すプレフィックス合計を作成します。このプレフィックスの合計については、k未満の最大結果が見つかり、このインデックスが結果になります。ここでは、プレフィックスの合計が任意のサイズでkより大きい場合、残りのすべての合計がより小さい場合、サイズ-1の長さのすべてのサブアレイの合計はk未満になります。

例

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

#include<iostream>
using namespace std;
int calcSubArraySize(int arr[], int n, int k){
   int prefixSum[n + 1];
   prefixSum[0] = 0;
   for (int i = 0; i < n; i++)
   prefixSum[i + 1] = prefixSum[i] + arr[i];
   // Searching size
   int maxLen = −1;
   int start = 1, end = n;
   int mid, i;
   while (start <= end){
      int mid = (start + end) / 2;
      for (i = mid; i <= n; i++){
         if (prefixSum[i] − prefixSum[i − mid] > k)
         break;
      }
      if (i == n + 1){
         start = mid + 1;
         maxLen = mid;
      }
      else
      end = mid − 1;
   }
   return maxLen;
}
int main(){
   int arr[] = {4, 1, 2, 3};
   int n = sizeof(arr) / sizeof(arr[0]);
   int k = 9;
   cout<<"The maximum subarray size, such that all subarrays of that
   size have sum less than k is "<<calcSubArraySize(arr, n, k);
   return 0;
}

出力

この方法は効率的ですが、問題を解決するためにより良いアプローチをとることができます。

このアプローチでは、サブ配列の合計を見つけるためにスライディングウィンドウ法を使用します。すべての要素を取得することから始めて、合計がkを超えるまでの長さを見つけます。次に、すべてのサブアレイの合計が0以下であるサブアレイの最大サイズである長さ-1を返します。

例

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

#include <iostream>
using namespace std;
int calcSubArraySizeSW(int arr[], int n, int k){
   int maxLen = n;
   int subArraySum = 0;
   int start = 0;
   for (int end = 0; end < n; end++){
      subArraySum += arr[end];
      while (subArraySum > k) {
         subArraySum −= arr[start];
         start++;
         maxLen = min(maxLen, end − start + 1);
         if (subArraySum == 0)
            break;
      }
      if (subArraySum == 0) {
         maxLen = −1;
         break;
      }
   }
   return maxLen;
}
int main(){
   int arr[] = { 4, 1, 3, 2, 6 };
   int k = 12;
   int n = sizeof(arr)/ sizeof(arr[0]);
   cout<<"The maximum subarray size, such that all subarrays of that
   size have sum less than k is "<<calcSubArraySizeSW(arr, n, k);
   return 0;
}

出力

The maximum subarray size, such that all subarrays of that size have sum
less than k is 4