[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