数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究在 C++ 中查找大小为 k 的子数组的最大（或最小）和
在这个问题中，我们给定一个数组 arr[] 和一个数字 k。我们的任务是查找大小为 k 的子数组的最大（或最小）和。
让我们举个例子来理解这个问题，
输入：arr[] = {55, 43, 12, 76, 89, 25, 99} , k = 2
输出：165
解释
大小为 2 的子数组的和 = 76 + 89 = 165
解决方案方法
解决此问题的一种简单方法是找到所有大小为 k 的子数组，然后返回具有最大值的和。
另一种方法是使用滑动窗口，我们将找到大小为 k 的子数组的和。对于下一个大小为 k 的子数组，我们将减去最后一个索引元素并添加下一个索引元素。
然后返回具有最大值的子数组和。
程序说明解决方案的工作原理，
示例
#include <iostream>
using namespace std;
int findMaxSumSubarray(int arr[], int n, int k) {
if (n < k) {
cout << "Invalid";
return -1;
}
int maxSum = 0;
for (int i=0; i<k; i++)
maxSum += arr[i];
int curr_sum = maxSum;
for (int i=k; i<n; i++) {
curr_sum += arr[i] - arr[i-k];
maxSum = max(maxSum, curr_sum);
}
return maxSum;
}
int main() {
int arr[] = {55, 43, 12, 76, 89, 25, 99};
int n = sizeof(arr)/sizeof(arr[0]);
int k = 2;
cout<<"The sum of subarray with max sum of size "<<k<<" is "<<findMaxSumSubarray(arr, n, k);
return 0;
}输出
The sum of subarray with max sum of size 2 is 165
更新于： 2021年1月25日
340 次查看
广告