最大子数组大小，以便在C ++程序中所有具有该大小的子数组的总和小于k
在这个问题中，我们得到了一个数组arr[]，该数组由n个正整数和一个整数k组成。我们的任务是创建一个程序来查找最大子数组大小，以使该大小的所有子数组的总和小于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的子数组。为此，我们将创建一个前缀sum，它表示直到给定索引的元素之和。对于此前缀总和，我们将找到小于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];
//搜索尺寸
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;
}输出结果
这种方法是有效的，但可以提出一种更好的方法来解决该问题，
在这种方法中，我们将使用滑动Window方法查找子数组的总和。从取所有元素开始，我们将找到总和保持在k以上的长度。然后返回长度−1，这是所有子数组之和小于或等于0的子数组的最大大小。
示例
该程序说明了我们解决方案的工作原理，
#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