数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装学
法学C++程序中，最大子数组大小，使得所有该大小的子数组的和都小于k
在这个问题中，我们得到一个包含n个正整数的数组arr[]和一个整数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的子数组。为此，我们将创建一个前缀和，表示直到给定索引的元素之和。对于此前缀和，我们将找到小于k的最大结果，其索引将是我们的结果。在这里，我们使用了这样一个事实：如果对于任何大小，前缀和都大于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];
// Searching size
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;
}输出
这种方法效率很高，但可以采用更好的方法来解决这个问题：
在这种方法中，我们将使用滑动窗口法来查找子数组的和。首先取所有元素，我们将找到和保持在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
更新于：2020年12月9日
浏览量 188
广告