問題タブ [kadanes-algorithm]

N 個の要素からなる配列 A が与えられます。私たちのタスクは、次の操作を 1 回だけ適用した後で、部分配列の最大和を見つけることです。

. 任意の部分配列を選択し、その中のすべての要素をゼロに設定します。

例:- 配列が -1 4 -1 2 の場合、答えは 6 です。これは、インデックス 2 で -1 を部分配列として選択して 0 にすることができるためです。したがって、操作を適用した後の結果の配列は、-1 4 0 2 になります。サブアレイの最大合計は 4+0+2 = 6 です。

私のアプローチは、最小合計部分配列の開始インデックスと終了インデックスを見つけ、その部分配列のすべての要素を 0 にしてから、最大合計部分配列を見つけることでした。しかし、このアプローチは間違っています。

自分の頭がアルゴリズムに向いていないと感じたことはありますか?

最大部分配列の問題を解決しようとしたところ、Codewars でこの解決策に出くわしました。

を使用して線形時間の複雑さでこの問題を解決する方法を理解していますKadane's algorithm:

しかし、最初のソリューションが機能する理由がわかりません。その背後にある考えを理解することはできません。こぶを乗り越えるのに少し助けが必要な気がします。

編集：ここにいくつかの例を含むCodepenがあります

以下はコード スニペットです。部分配列の最大合計は 6 ですが、7 として計算されていることがわかります
。Kadane のアルゴリズムはここで失敗していますか?!

これは、1 回のパスで解決する必要がある典型的な問題です。0、1、および 2 のみを含む配列が与えられます。O(1) 補助空間で 1 回のパスで配列をソートする必要があります。より明確な値を含む配列に対してそのようなワンパスソリューションが存在するかどうか、およびワンパスソリューションが存在する個別の値の数の制限は何なのか疑問に思っていました。