algorithm - アルゴリズムの分析 - 何かアイデアはありますか?

Question

重複の可能性:
少なくとも長さ L の最大連続部分列合計

X = {x1, x2, ··· , xn} を任意の数列 (正または負) とする。O(n) 時間のアルゴリズムを与えて、すべての連続する部分列にわたって合計が最大になる連続する要素 xi,xi+1,···,xj の部分列を見つけます。たとえば、X = {2,5, −10, 3, 12, −2, 10, −7, 5} の場合、{3, 12, −2, 10} が解です。

Answer 1

この問題は、動的計画法を使用して解決できます。入力が配列であるとしましょう。同じ長さaの配列を作成できます。S以下は、問題の再現関係です。

S[i] = S[i-1] + a[i] > a[i] ? S[i-1] + a[i] : a[i]

規範事例：S[0] = a[0]

max最大合計を追跡するために保管してください。最後に を返しますmax。

Answer 2

答えはhttp://en.wikipedia.org/wiki/Maximum_subarray_problem#Kadane.27s_algorithmです

このアルゴリズムの背後にある考え方は、長さ N の配列の問題の真の最大部分配列を知っていると仮定し、さらに両端から始まる最大部分配列を知っているということです。(理論的根拠: 端に接する最大シーケンスを知っていると仮定し、最後に要素を徐々に追加すると、ある時点で最後に追加された要素が同じ要素になるため、真の最大部分配列を見逃すことはできません。真の最大部分配列の端点として。)余分な要素を追加すると、最後に接続された最長の部分配列の長さが増加する可能性があります。サブアレイの合計が 0 を下回る場合は、リセットします。真の最大部分配列の現在の最良の候補解を超える場合は、最良の候補解を置き換えます。

あるいは、統合の力を利用することもできます。(これは、無料で実行できる O(N) パスです。無料で微分することもできます。) 次に、すべての極値を調べて、2 つの極値 MIN と MAX を検索し、MAX が MIN の右側にあるようにします (またはそれ以外の場合は、最も負の合計を見つけることになります)、また MAX-MIN (連続した合計) が最大になるようにします。このサブ問題を力ずくで解決することもできます (極端な数が sqrt(N) よりも小さい場合は O(N) のままです)、またはより効率的な方法で解決することもできます [ここでいくつかのヘルプを使用できます]。

Answer 3

O(n)これは、線形時間で見つけやすいすべての非負要素のシーケンスです。