Best Time to Buy and Sell Stock — LeetCode 121 Python Solution

The problem

You are given an array prices where prices[i] is the price of a given stock on the ith day. You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Example

Input

prices = [7,1,5,3,6,4]

Output

5

Explanation

Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.

Python solution

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        ans, mi = 0, inf
        for v in prices:
            ans = max(ans, v - mi)
            mi = min(mi, v)
        return ans

Complexity

Pattern: Dynamic Programming

Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 121. Best Time to Buy and Sell Stock 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