私は正の整数値を含む4×n行列を持っています。次の出力の対象として、M_ {1、j_1}、M_ {2、j_2}、M_ {3、j_4}、M_ {4、j_4}を持つように各行から1つの値を選択します。合計を最大化する要素をピッキングする
がありM_ {J_2 2、}これの高速アルゴリズム？
単純に2行だけの場合：j_2を順次インクリメントし、すべてのM_ {2、j_2}を検査して、同時に最適なM_ {1 、j_1}の値（j_1 < j_2のM_ {2、j_2}より小さい最大のM_ {1、j_1}）、これらの値の最大合計を求めます。これを行3と行4に拡張する必要がある場合は、この最大値を（各j_2に対して）いくつかの配列に書いてください。
最適なM_ {1、j_1}値を得るための明白な方法は、M_ {1,1} ... M_ {1、j_2-1}のプレフィックスのバイナリ検索ツリーを維持することです。このツリーのM_ {2、j_2}値の先祖を見つけます。しかし、これは最適以下のO（n log n）アルゴリズムを導く。
O（n）時間の複雑さについては、より単純なデータ構造、すなわちスタックが必要です。最初の行のいくつかの要素をスタックに追加する前に、現在の要素よりも小さいか等しいすべてをスタックからポップします（これにより、スタックは強く降順に保たれます）。 M_ {2、j_2}の値の前の値を検索するときは、最後の値を除いてM_ {2、j_2}より小さいか等しい値をすべてスタックからポップし、それを最適なM_ {1、j_1}値として使用します。
3行目を追加するには、最初の2行と3行目の最大値に2行アプローチを適用します。 4番目の行を追加するには、同じアルゴリズムをもう一度適用します。
全体のアルゴリズムは行列を3回スキャンし、要素をスタックに/から3×n回押してポップし、時間の複雑さをO（n）にします。 2つの中間配列を格納するために必要なO（n）の余分なスペースは、プレフィックスの最大値をオンザフライで計算すると除去できます。しかし、スタックのためにはまだO（n）スペースが必要です。入力行列の内容を破壊することが許されていれば、O（1）余分なスペースで問題を解決することができます：3つのスタックを3つのスタックまたは1つのスタック+ 2つの中間の配列に再利用するだけです（実装は非常に難しいでしょう最適値の指標を報告する必要がある）。
これは非常にきれいで清潔なソリューションです。ありがとうございました。 – eleanora
最初からすべてを理解してくれてうれしいです。それでも私は、いくつかの重要な詳細が欠けていて、答えを更新していることがわかりました –
私はあなたが2行の線形時間に近いところでそれを解決できるとは思わないので、4のためにそうすることはありそうにありません。
私は最良のアプローチは動的プログラミングだと思います：連続した行（2..4）ごとに、その行の各要素について計算できる最良の合計を見つけ出します）、下の行の最良の合計を計算したと仮定して、行4の最良のものを取ってください。
「高速」を定義します。特に、あなたが思いついたアルゴリズム（あなたが共有するのを忘れてしまった）よりもずっと速い。 –
@ScottHunter私はそれが線形時間に近いことを意味します。私が知っている唯一の方法は完全に素朴です。 – eleanora