Best Time to Buy and Sell Stock

連続する日数分の株価が与えられます。1日につき価格は1つです。ある日に1株買い、その後の日に売ることができます。利益は売値から買値を引いた額で、できるだけ大きな利益を得たいとします。どの取引でも損をする場合は、取引をせず、利益は0です。

価格が [7, 2, 5, 9, 1, 4] の場合を考えてみましょう。1日目に2で買い、3日目に9で売ると7の利益が得られ、ほかの日の組み合わせでこれを上回ることはありません。4日目に1で買うのは魅力的に見えますが、その後の日に売れる価格は4だけなので、その取引で得られる利益はわずか3です。

すべての日の組み合わせを試す方法でも解けますが、価格のリストが長い場合は遅すぎます。代わりに、日々の価格を1回たどるだけで解けます。今日売るなら、これまでで最も安い日に買っておくのが最善なので、進みながらその最安値を記録しておきます。今日の最善の利益は今日の価格から最安値を引いた値で、答えはそのような利益のうち最大のものです。

maxProfitという名前の関数を作成してください。この関数は整数のリストpricesを受け取ります。ここで、prices[i]はi日目の株価を表し、ある日に買ってそれより後の日に売ることで得られる最大利益を返します。利益が出る取引がない場合は、0を返してください。

制約: 1 ≤ prices.length ≤ 10^5、0 ≤ prices[i] ≤ 10^4。