数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会研究
时尚研究
法律研究C++ 中包含至少 k 个数的最大子数组和
让我们了解完成该程序的步骤。
- 初始化数组。
- 初始化大小为 n 的 max\_sum 数组。
- 查找每个索引的最大和并将其存储在 max\_sum 数组中。
- 计算所有元素的总和并将其存储在变量 sum 中。
- 编写一个从 i = k 到 n 循环的循环。
- 将 a[i] - a[i - k] 添加到 sum 中。
- 使用结果、和的最大值更新结果。
- 使用结果、和 + max\_sum[i - k] 的最大值更新结果。
示例
让我们看看代码。
#include<bits/stdc++.h>
using namespace std;
int getMaxSum(int a[], int n, int k) {
int maxSum[n];
maxSum[0] = a[0];
int currentMax = a[0];
for (int i = 1; i < n; i++) {
currentMax = max(a[i], currentMax+a[i]);
maxSum[i] = currentMax;
}
int sum = 0;
for (int i = 0; i < k; i++) {
sum += a[i];
}
int result = sum;
for (int i = k; i < n; i++) {
sum += a[i] - a[i-k];
result = max(result, sum);
result = max(result, sum + maxSum[i-k]);
}
return result;
}
int main() {
int a[] = {5, 3, 7, -5, 6, 2, 1};
int k = 6;
cout << getMaxSum(a, 7, k) << endl;
return 0;
}输出
如果你运行以上代码，你将得到以下结果。
19
结论
如果你对本教程有任何疑问，请在评论区提及。
更新时间：09-Apr-2021
322 次浏览
广告