[LeetCode] [Python] 123。株式を売買するのに最適な時期III



123



あなたがそのための配列を持っているとしましょう 3番目の要素は、その日の特定の株式の価格です。

最大の利益を見つけるためのアルゴリズムを設計します。あなたはせいぜい完了することができます トランザクション。



注意:
同時に複数の取引を行うことはできません(つまり、再度購入する前に株式を売却する必要があります)。

アイデア2:2つのトラバーサル。



  • 初めて左から右へ、最初から最初へ 日、達成できる最大の利益。
  • 右から左への2回目、最初から取得 その日から最後の日まで達成できる最大の利益。

最後に、 (0<= i < size), which divides the array into two parts, and the sum of the maximum returns of the two parts is the final benefit. Find out which one is the biggest.

最初のトランザクションでは配列すべてを2、[0、i]に、2番目のトランザクションでは[i、prices.length-1]に配置できます。
iポイントを指定すると、[0、i]エリアの終わりとしてiポイントで商品を販売し、[i、価格]としてiポイントで商品を購入できます。長さ-1]領域の始まり、

class Solution(object): def maxProfit(self, prices): ''' :type prices: List[int] :rtype: int ''' if not prices: return 0 pre = [] low = float('inf') res = 0 for i in xrange(len(prices)): low = min(prices[i], low) res = max(res, prices[i] - low) pre.append(res) high = float('-inf') res = 0 post = [] total_max = 0 for i in xrange(len(prices)-1, -1, -1): high = max(prices[i], high) res = max(res, high - prices[i]) post.append(res) total_max = max(total_max, pre[i] + res) return total_max