本質は何ですか
この記事では、過去5年間のドル/ルーブル為替レートの差から最も利益を得ることができる期間を見つけることを提案しています。
ロシア語では、問題の名前は、配列内のサブ配列要素の最大合計とほぼ同じように聞こえます。 この記事では、計算アルゴリズムとその作業の結果を示します。
どうやってこれに来たの
彼は最近、優れたCLRS本（ トーマスH.コーメン、チャールズE.レイザーソン、ロナルドL.リベスト、クリフォードスタイン。アルゴリズムの紹介、第3版 ）を読み始めました。 推測するのは難しいことではないので、この本はコンピュータサイエンスの基本的な知識を概説しています。
本のセクションの1つは、この問題を解決するアルゴリズムの実装をリードしています。 知識を統合し、自分の興味を満足させるために、過去5年間のルーブルに対するドルの為替レートのデータにそれを適用することにしました。
問題の本質
過去5年間のグラフからわかるように、ドルは大きく変化しています。 そして、最良の取引は絶対最小で購入し、その後の極大で販売することであると想定するのは合理的です（「目で」検出するのはそれほど簡単ではない場合があります）。
このステートメントを確認しましょう。
解決策
最も簡単な解決策は、「正面に行き」、それを検索してサブアレイのすべての組み合わせの合計を見つけ、それらを比較して最大値を見つけることです。しかし、この解決策は、O（n ^ 2）より最適。
解決策により、入力配列を中央から2つのサブ配列に再帰的に分割し、各部分と部分、およびそれらの交点で最大合計を探します。 このプロセスにはO（n lg n）が必要です。これは非常に効果的です。
例を書いてみましょう：
www.oanda.com/currency/historical-ratesから.csvファイルの形式でデータを取得します
"2011-10-02","32.1914",,,,
"2011-10-01","32.0809",,,,
"2011-09-30","31.9086",,,,
"2011-09-29","31.7294",,,,
"2011-09-28","32.0421",,,,
"2011-09-27","32.2233",,,,
"2011-09-26","32.0980",,,,
"2011-09-25","32.0673",,,,
...
次に、データを読み取り、処理のために準備する必要があります。
courses = [] reader = csv.reader(open('data.csv', 'rb'), delimiter=',', quotechar='"') prev = 0 for row in reader: # cur = float(row[1]) # if prev == 0: prev = cur # value = [row[0], prev - cur, row[1]] prev = cur courses.insert(0, value)
ファイル内のデータは時間に関して逆順であるため、逆に挿入します。 データ処理中に、以前の-現在の毎日のコースの違いを探します。 私たちの仕事は、これらの違いの最大量を見つけることです。
def find_max_subarray(a, low, high): # if high == low: return low, high, a[low][1] else: # 2 mid = (low + high) / 2 # left_low, left_high, left_sum = find_max_subarray(a, low, mid) # right_low, right_high, right_sum = find_max_subarray(a, mid + 1, high) # - cross_low, cross_high, cross_sum = find_crossing(a, low, mid, high) if (left_sum >= right_sum) & (left_sum >= cross_sum): return left_low, left_high, left_sum elif (right_sum >= left_sum) & (right_sum >= cross_sum): return right_low, right_high, right_sum else: return cross_low, cross_high, cross_sum
また、クロス最大検索機能（中間から中間分割を通過）。
def find_crossing(a, low, mid, high): max_left = 0 max_right = 0 left_sum = -1e308 sum = 0 # for i in range(mid, low, -1): sum = sum + a[i][1] if sum > left_sum: left_sum = sum max_left = i max_right = 0 right_sum = -1e308 sum = 0 # for j in range(mid + 1, high): sum = sum + a[j][1] if sum > right_sum: right_sum = sum max_right = j return max_left, max_right, left_sum + right_sum
さて、私たちは興味のある結果を得る
min, max, sum = find_max_subarray(courses, 0, len(courses)-1) print courses[min] print courses[max] print sum
その結果、私は得た
['2008-07-16', 0.07420000000000115, '23.1269']
['2009-02-05', 0.12059999999999604, '36.1257']
13.1194
そして、少し遊び、2011年の下限日をシフトします
['2011-05-05', 0.006199999999999761, '27.2657']
['2011-09-26', 0.12530000000000285, '32.0980']
4.9576
すべてのコードはgist.github.com/1257729にあります
ご清聴ありがとうございました！