Best Time to Buy and Sell Stock III — LeetCode 123 Python Solution

The problem

You are given an array prices where prices[i] is the price of a given stock on the ith day. Find the maximum profit you can achieve.

Example

Input

prices = [3,3,5,0,0,3,1,4]

Output

6

Explanation

Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.

Python solution

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # 第一次买入，第一次卖出，第二次买入，第二次卖出
        f1, f2, f3, f4 = -prices[0], 0, -prices[0], 0
        for price in prices[1:]:
            f1 = max(f1, -price)
            f2 = max(f2, f1 + price)
            f3 = max(f3, f2 - price)
            f4 = max(f4, f3 + price)
        return f4

Complexity

Pattern: Dynamic Programming

Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 123. Best Time to Buy and Sell Stock III is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Dynamic Programming.

The dynamic programming guide has the Python template for the pattern and the 481 LeetCode problems that use it.

Related problems