C ++中具有至少k个数的最大和子数组

让我们看看完成程序的步骤。

• 初始化数组。

• 初始化大小为n的max_sum数组。

• 找到每个索引的最大和，并将其存储在max_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

结论