在本教程中,我们将讨论一个找到最大子数组大小的程序,以使该大小的所有子数组的总和小于k。
为此,我们将得到一个大小为N和整数k的数组。我们的任务是找到子数组的长度,以使给定数组中该长度的所有子数组的总和小于或等于k。
#include<bits/stdc++.h> using namespace std; //查找最大长度子数组 int bsearch(int prefixsum[], int n, int k) { int ans = -1; //执行二进制搜索 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; } //返回最大子数组大小 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