0

配列内の最大サブ配列を検出するためのアルゴリズムがあります (連続および非連続の両方)。ただし、それらのほとんどは、負の数と正の数の両方を持つことに基づいています。正の数のみでどのように行われますか?

一連の時間範囲にわたる株式の値の配列があります (配列には、連続するすべての月の値が含まれているとしましょう)。

[15.42, 16.42, 17.36, 16.22, 14.72, 13.95, 14.73, 13.76, 12.88, 13.51, 12.67, 11.11, 10.04, 10.38, 10.14, 7.72, 7.46, 9.41, 11.39, 9.7, 12.67, 18.42, 18.44, 18.03, 17.48, 19.6, 19.57, 18.48, 17.36, 18.03, 18.1, 19.07, 21.02, 20.77, 19.92, 18.71, 20.29, 22.36, 22.38, 22.39, 22.94, 23.5, 21.66, 22.06, 21.07, 19.86, 19.49, 18.79, 18.16, 17.24, 17.74, 18.41, 17.56, 17.24, 16.04, 16.05, 15.4, 15.77, 15.68, 16.29, 15.23, 14.51, 14.05, 13.28, 13.49, 13.12, 14.33, 13.67, 13.13, 12.45, 12.48, 11.58, 11.52, 11.2, 10.46, 12.24, 11.62, 11.43, 10.96, 10.63, 10.19, 10.03, 9.7, 9.64, 9.16, 8.96, 8.49, 8.16, 8.0, 7.86, 8.08, 8.02, 7.67, 8.07, 8.37, 8.35, 8.82, 8.58, 8.47, 8.42, 7.92, 7.77, 7.79, 7.6, 7.18, 7.44, 7.74, 7.47, 7.63, 7.21, 7.06, 6.9, 6.84, 6.96, 6.93, 6.49, 6.38, 6.69, 6.49, 6.76]

各要素について、最大のパーセンテージ ゲインが得られた 1 つの期間を特定するアルゴリズムが必要です。これは、在庫に応じて、1 か月の期間、数か月にわたる期間、または配列全体 (例: 120 か月) の場合があります。次に、パーセンテージ ゲインとリターン (元の価格に対する価格の変化。その期間のピーク価格と開始価格) の観点から、バーストを出力したいと考えています。

max subarray 型のアルゴリズムを組み合わせましたが、この問題は少し異なることに気付きました。配列には負の数がないため、これらのアルゴリズムは配列全体を周期として報告し、すべての要素の合計をゲインとして報告するだけです。

私が言及したアルゴリズムはこことここにあります。後者はマスター定理に基づいています。お役に立てれば。

Ruby でコーディングしていますが、疑似コードも歓迎します。

4

2 に答える 2

2

あなたは間違った方向に進んだと思います...
私はRubyに精通していませんが、あなた自身の言葉を使用して疑似コードでアルゴリズムを構築しましょう:

一定期間の株式の値を含む配列を取得しました (この例では、各要素が 1 か月の株式の値であり、配列には連続するすべての月の値が含まれているとします)。

この配列StockValuesに という名前を付けます。その長さは で与えられlength(StockValues)ます。1 ベースであると仮定します (最初の項目は で取得されますStockValues[1]) 。

配列を分析し、各要素について、価格の上昇率が最大だった 1 つの期間を特定するアルゴリズムが必要です。

i特定のインデックスについて、どのインデックスjでj>i最大のゲインがパーセントで得られるか、つまりいつ最大になるかを知りたいとしgain=100*StockValues[j]/StockValues[i]-100ます。

次に、パーセンテージゲインとリターン（元の価格に対する価格の変化。つまり、期間のピーク価格と開始価格）の観点から、バーストを出力したいと考えています。

burst=gain=100*StockValues[j]/StockValues[i]-1002 つの値を取得したいとしますreturn=StockValues[j]-StickValues[i]
。最初のステップは、配列をループし、各要素に対して 2 番目のループを実行して、ゲインが最大になるタイミングを見つけます。最大値が見つかったら、必要な値を Result という別の配列に保存します。 (この配列が無効な値で初期化されていると仮定しましょう。たとえば、burst=-1 のように、任意の期間にわたってゲインが見つからないことを意味します) 

for i=1 to length(StockValues)-1 do
  max_gain=0
  for j=i+1 to length(StockValues) do
    gain=100*StockValues[j]/StockValues[i]-100
    if gain>max_gain then
      gain=max_gain
      Result[i].burst=gain
      Result[i].return=StockValues[j]-StockValues[i]
      Result[i].start=i
      Result[i].end=j
      Result[i].period_length=j-i+1
      Result[i].start_price=StockValues[i]
      Result[i].end_price=StockValues[j]
    end if
  end for
end for

このアルゴリズムは最小の期間を提供することに注意してください。同じゲイン値を持つ期間が複数ある場合、これを に置き換えるgain>max_gainと最長の期間が得られます。gain>=max_gain正またはゼロのゲインのみがリストされます。ゲインがまったくない場合、Result には無効な値が含まれます。1 を超える期間のみがリストされます。1 の期間が受け入れられる場合、考えられる最悪のゲインは 0% になり、ループの行き先と開始点iを変更する必要があります。length(StockValues)ji

于 2012-09-19T00:08:49.767 に答える
1

これは、何かが欠けていない限り、実際には数日間の作業のようには聞こえません:p。

# returns array of percentage gain per period
def percentage_gain(array)
  initial = array[0]
  after = 0
  percentage_gain = []
  1.upto(array.size-1).each do |i|
    after = array[i]
    percentage_gain << (after - initial)/initial*100
    initial = after
  end
  percentage_gain
end

# returns array of amount gain $ per period
def amount_gain(array)
  initial = array[0]
  after = 0
  amount_gain = []
  1.upto(array.size-1).each do |i|
    after = array[i]
    percentage_gain << (after - initial)
    initial = after
  end
  amount_gain
end

# returns the maximum amount gain found in the array
def max_amount_gain(array)
  amount_gain(array).max
end

# returns the maximum percentage gain found in the array
def max_percentage_gain(array)
  percentage_gain(array).max
end

# returns the maximum potential gain you could've made by shortselling constantly.
# i am basically adding up the amount gained when you would've hit profit.
# on days the stock loses value, i don't add them.
def max_potential_amount_gain(array)
  initial = array[0]
  after = 0
  max_potential_gain = 0
  1.upto(array.size-1).each do |i|
    after = array[i]
    if after - initial > 0
      max_potential_gain += after - initial
    end
    initial = after
  end
  amount_gain
end

array = [15.42, 16.42, 17.36, 16.22, 14.72, 13.95, 14.73, 13.76, 12.88, 13.51, 12.67, 11.11, 10.04, 10.38, 10.14, 7.72, 7.46, 9.41, 11.39, 9.7, 12.67, 18.42, 18.44, 18.03, 17.48, 19.6, 19.57, 18.48, 17.36, 18.03, 18.1, 19.07, 21.02, 20.77, 19.92, 18.71, 20.29, 22.36, 22.38, 22.39, 22.94, 23.5, 21.66, 22.06, 21.07, 19.86, 19.49, 18.79, 18.16, 17.24, 17.74, 18.41, 17.56, 17.24, 16.04, 16.05, 15.4, 15.77, 15.68, 16.29, 15.23, 14.51, 14.05, 13.28, 13.49, 13.12, 14.33, 13.67, 13.13, 12.45, 12.48, 11.58, 11.52, 11.2, 10.46, 12.24, 11.62, 11.43, 10.96, 10.63, 10.19, 10.03, 9.7, 9.64, 9.16, 8.96, 8.49, 8.16, 8.0, 7.86, 8.08, 8.02, 7.67, 8.07, 8.37, 8.35, 8.82, 8.58, 8.47, 8.42, 7.92, 7.77, 7.79, 7.6, 7.18, 7.44, 7.74, 7.47, 7.63, 7.21, 7.06, 6.9, 6.84, 6.96, 6.93, 6.49, 6.38, 6.69, 6.49, 6.76]
于 2012-09-19T00:09:46.617 に答える