C++で少なくともk個の数値を持つ最大の合計サブ配列

プログラムを完了するための手順を見てみましょう。

• アレイを初期化します。
• サイズnのmax_sum配列を初期化します。
• すべてのインデックスの最大合計を見つけて、max_sum配列に格納します。
• すべての要素の合計を計算し、それを可変合計に格納します。
• i=kからnまで繰り返すループを作成します。
  • 合計にa[i]--a[i--k]を追加します。
  • 結果の最大値、合計で結果を更新します。
  • 結果の最大値、合計+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

結論

チュートリアルに質問がある場合は、コメントセクションにそのことを記載してください。