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