最大子数组大小，以便在C ++程序中所有具有该大小的子数组的总和小于k

Z时代
2024-01-10
分类：综合

在这个问题中，我们得到了一个数组arr []，该数组由n个正整数和一个整数k组成。我们的任务是创建一个程序来查找最大子数组大小，以使该大小的所有子数组的总和小于k。

问题描述-我们需要找到子数组的最大大小，以使所有根据该数组的元素创建的子数组的大小之和小于或等于k。

让我们举个例子来了解这个问题，

输入项

arr[n] = {4, 1, 3, 2}, k = 9

输出结果

说明

大小为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;
}