C ++中具有至少k个数的最大和子数组
让我们看看完成程序的步骤。
初始化数组。
初始化大小为n的max_sum数组。
找到每个索引的最大和，并将其存储在max_sum数组中。
计算所有元素的总和并将其存储在可变总和中。
编写一个从i=k迭代到n的循环。
将a[i]-a[i-k]加和。
用结果的总和，总和更新结果。
用结果的最大值sum和max_sum[i-k]更新结果。
示例
让我们看一下代码。
#include输出结果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