algorithm - サブ配列の長さが k 以下になるように連続するサブ配列の最大和を求めますか?

Question

3 つ以上のサブ配列が存在する場合は、長さの短いサブ配列を返す必要があります。

サブアレイの長さとその合計のみに関心があります。

これは総当たりを使用して O(n^2) で解決できることは知っていますが、これを行う効率的な方法を探しています。また、スライディング ウィンドウの概念を使用して O(n) でこれを解決しようとしましたが、後で失敗する場合があることに気付きました。

これを効率的に行うにはどうすればよいでしょうか。

Answer 1

Kadane のアルゴリズムを参照することをお勧めします。指定された配列から合計が最大の連続する部分配列を見つけます。これは O(n) で行います。あなたの問題は、長さを「k」に制限します。したがって、Kadane's で長さ <= k をチェックするだけです。