C++에서 해당 크기의 모든 하위 배열의 합이 k보다 작도록 하는 최대 하위 배열 크기

이 자습서에서는 해당 크기의 모든 하위 배열의 합이 k보다 작도록 최대 하위 배열 크기를 찾는 프로그램에 대해 설명합니다.

이를 위해 크기 N과 정수 k의 배열이 제공됩니다. 우리의 임무는 주어진 배열에서 해당 길이의 모든 하위 배열의 합이 k보다 작거나 같도록 하위 배열의 길이를 찾는 것입니다.

예

#include<bits/stdc++.h>
using namespace std;
//finding maximum length subarray
int bsearch(int prefixsum[], int n, int k) {
   int ans = -1;
   //performing binary search
   int left = 1, right = n;
   while (left <= right) {
      int mid = (left + right) / 2;
      int i;
      for (i = mid; i <= n; i++) {
         if (prefixsum[i] - prefixsum[i - mid] > k)
         break;
      }
      if (i == n + 1) {
         left = mid + 1;
         ans = mid;
      }
      else right = mid - 1;
   }
   return ans;
}
//returning maximum subarray size
int maxSize(int arr[], int n, int k) {
   int prefixsum[n + 1];
   memset(prefixsum, 0, sizeof(prefixsum));
   for (int i = 0; i < n; i++)
   prefixsum[i + 1] = prefixsum[i] + arr[i];
   return bsearch(prefixsum, n, k);
}
int main() {
   int arr[] = {1, 2, 10, 4};
   int n = sizeof(arr) / sizeof(arr[0]);
   int k = 14;
   cout << maxSize(arr, n, k) << endl;
   return 0;
}

출력

2