最大子数组大小，以便在C ++中具有该大小的所有子数组的总和小于k
在本教程中，我们将讨论一个找到最大子数组大小的程序，以使该大小的所有子数组的总和小于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
热门推荐
6 保研的祝福语简短
10 年轻20岁祝福语简短
11 朋友结婚祝福语信息简短
12 女孩婚礼贺卡祝福语简短
13 30段点歌简短祝福语
14 虎年春节祝福语图文简短
15 写给后妈祝福语大全简短
16 简短回复生日祝福语
17 校长送毕业祝福语简短
18 毕业立体贺卡祝福语简短