分裂と征服を使用したソートアルゴリズム

Question

これは株式マーケティングの問題のようなものです。日々の最大利益を得る方法について質問しているのは混乱していますか？アルゴリズムの時間複雑さはO（n）またはO（n log2 n）であることがわかります。

入力は、株価の配列であるAです。 1日目は、1日目に買って翌日に売ることで最大の利益を得ることができます。利便性のため、最終日のベストトレードを定義することができます。これは単純に-A [n]（最終日に購入すれば売ることはできません。 Aの毎日の最大利益を含む配列を返すアルゴリズムの擬似コードを返します。

更新：最大の利益を得る方法を理解しており、同様のアルゴリズムを分割するマージソートとして使用できますこの最大の利益を見つけることを征服する。私の質問は、最大の利益を見つけるために時間の複雑さO（n）を使用する別の方法（アルゴリズム）は何ですか、あるいは私はこの方法でどのようにアプローチできますか？

Answer 1

それはO（n）のだから、あなたがこの問題を考えることができる一つの方法は、ループのための1つを使用している、私はあなたにいくつかのヒントを与えることができます。

for i from 0 to n: 
     if (A[i] < A[min]) // find the minimum value of stock 
      min = i; 
     profit = A[i] - A[min] // get the profit 
     if (profit > maxProfit) { // compares the profits 
      maxProfit = profit // always update the max profit 

Answer 2

あなたが一日iに購入した場合、あなたが作ることができる最大の利益はAmax(i) - A[i]、Amax(i)は日i後を発生し、最高価格である です。 アルゴリズムの仕様を読むと、配列がM[i] = Amax(i) - A[i]で定義された配列Mを構築して返すことになります。

iの後に発生する最高価格は、 A[i+i]と、i + 1の後に発生する最高価格のうち大きい方です。

最後の段落は、あなたが見るかもしれない「典型的な」再帰は、i番目の値が i + 1番目の値ではなく、他の方法で回避に依存 と違っことを除いて、再帰的な関係を、提供します。 しかし、幸いにも、あなたはすでにn番目の値と の値が0であること、つまりnの後に0が得られることを既に知っています。 したがって、O（n）時間で実行できる、 1,2、...、n - 1日の値を把握するだけで済みます。 これらの値のいずれかを見つけるたびにAmax(i)、を使用してMのいずれかのエントリを設定できます。

---

あなたは、これが問題文で必要とされていないが、任意の単一日の株式1株を購入し、それ以降の日に販売することによって行うことができる最大の利益、1時間 を（見つけたい場合は、あなたがO（n）時間に行うことができるMの最大値を見つけなければなりません。

株を売買する一連の行動によって最大の利益を上げることが目標の場合は、株式が地元の最低価格にあるときはいつでもできるだけ多くの株式を購入することができます最初の日の前に無限の価格）と地元の最高価格に達するたびにすべてを販売しています。 O（n）時間内にすべてのローカル最小値と最大値を特定し、いずれかの方向にAをスキャンし、開始金額を指定すると、ローカル最小値のリストを使用してO（n）最大値はAです。 （しかし、これは元の問題文があなたに構築を依頼した配列を使用しません。なぜなら、その配列は購入した株式の数も、複数のトランザクションの可能性も考慮していないからです。）

は、二つのパスアルゴリズムの各パスはO（N）時間がかかる場合、全体としてのアルゴリズムはO（N）時間を要することに注意してください。