数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++ 中小于等于给定和的最大子数组和
在这个问题中，我们给定一个数组和一个和。我们的任务是创建一个程序，在 C++ 中找到和不大于给定和的最大子数组和。
我们必须找到长度小于等于 n 且和不大于给定和的任何长度的子数组。
让我们举个例子来理解这个问题：
输入 − array = {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
更新于：2020年6月3日
612 次浏览
广告