ALDA1_1_D - Maximum Profitある通貨について、時刻 t における価格 Rt (t=0,1,2,,,n−1)が入力として与えられるので、価格の差 Rj−Ri (ただし、j>i とする) の最大値を求めるというプログラムです。 最初の行に整数 n が与えられ、続く n 行に整数 Rt (t=0,1,2,,,n−1) が順番に与えられます。 注意点としては、通貨の取引なので時間を過去に遡ることはできないということです。 ですので、単純に与えられる入力の最大値と最小値から求めることはできません。 ここでは、与えられる入力を読み込む毎にその時刻までの価格の最小値(r_min)と今までの利益の最大値(g_max)を保持するようにしています。 入力の数は 2≤n≤200,000 という制約があるため、まず初めに2つ入力を読み込んで そこから最初の g_max と r_min を算出しています。 あとは入力を1つ読み込む毎に g_max と r_min を更新して、最後に g_max を出力しています。 感想株の取引などはあの頃買っておけば今頃。。。なんて思いがちですが 時間はどうやっても逆戻りできず、前に進むのみです。 悔いの残らないように今を大切に生きていきましょう!
0 コメント
あなたのコメントは、承認後に掲載されます。
メッセージを残してください。 |