C ++中总和小于或等于给定总和的最大总和子数组

在这个问题上，我们得到一个数组和一个和。我们的任务是创建一个程序，该程序将找到总和小于或等于c ++中给定总和的最大总和子数组。

我们必须找到任何长度小于或等于n且总和小于或等于给定总和的子数组。

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

输入-数组= {3，5，1，8，2，9}，sum = 25

输出-25

说明-总和小于或等于25的子数组是{5，1，8，2，9}

找到最大总和子数组的一种简单方法是遍历数组，找到所有子数组的总和，然后找到最接近或相等的总和。但是由于需要两个循环，因此该方法的时间复杂度为O（n * n）。

解决此问题的更有效方法是使用滑动窗口方法。在其中，我们将使用最大和检查当前和，并根据比较将元素添加或减少到窗口中。

示例

该程序说明了我们解决方案的工作原理，

#include <iostream>
using namespace std;
int findMax(int a, int b){
   if(a>b)
      return a;
   return b;
}
int maxSumsubarray(int arr[], int n, int maxSum){
   int sum = arr[0], overallMax = 0, start = 0;
   for (int i = 1; i < n; i++) {
      if (sum <= maxSum)
      overallMax = findMax(overallMax, sum);
      while (sum + arr[i] > maxSum && start < i) {
         sum -= arr[start];
         start++;
      }
      sum += arr[i];
   }
   if (sum <= maxSum)
      overallMax = findMax(overallMax, sum);
   return overallMax;
}
int main(){
   int arr[] = {3, 1, 4, 7, 2, 9, 5};
   int n = sizeof(arr) / sizeof(arr[0]);
   int sum = 20;
   cout<<"The maximum sum of subarray with sum less than or equal to "<<sum<<" is "<<maxSumsubarray(arr, n, sum);
   return 0;
}

输出结果

The maximum sum of subarray with sum less than or equal to 20 is 18