Kích thước mảng con tối đa, sao cho tất cả các mảng con có kích thước đó có tổng nhỏ hơn k trong C ++

Trong hướng dẫn này, chúng ta sẽ thảo luận về một chương trình để tìm kích thước mảng con tối đa, sao cho tất cả các mảng con có kích thước đó có tổng nhỏ hơn k.

Đối với điều này, chúng ta sẽ được cung cấp một mảng kích thước N và một số nguyên k. Nhiệm vụ của chúng ta là tìm độ dài của mảng con sao cho tất cả các mảng con có độ dài đó trong tổng mảng đã cho nhỏ hơn hoặc bằng k.

Ví dụ

#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;
}

Đầu ra

2