Algorithms are now big factories, foreign companies hard indicators. Development, test, test, always want to go up around the open.

Topic describes

【 array 】 【 Dynamic programming 】

Given an array prices, its ith element prices[I] represents the price of a given stock on day I. You can only buy the stock on one day and sell it on a different day in the future. Design an algorithm to calculate the maximum profit you can make. Return the maximum profit you can make from the transaction. If you can't make any profit, return 0.Copy the code

Subject address: leetcode-cn.com/problems/be…

The sample

Example 1

Input: [7,1,5,3,6,4] output: 5 explanation: buy on day 2 (stock price = 1) and sell on day 5 (stock price = 6), maximum profit = 6-1 = 5. Note that the profit cannot be 7-1 = 6, because the selling price needs to be higher than the buying price; Also, you can't sell stocks before you buy them.Copy the code

Example 2

Input: prices = [7,6,4,3,1] output: 0 explanation: in this case, no transaction is completed, so the maximum profit is 0.Copy the code

The problem solving

Brute force cracking has a timeout risk.

The idea of a traversal:

If you have a variable that records the minimum price min_price as you iterate through prices for each day, it’s easy to figure out how much profit you can make at the current price.

Min_price = float(” INF “), and I’m using infinity to initialize the minimum price, because the price must be positive, but I don’t know how much.

Start traversal. In each traversal, compare the current price with min_price, and take the smallest to update the minimum price.

Then calculate the profit you can make at the current price, store the profit you can make at the current price with max_profit, initialize it to 0. The current price price-min_price is maximized after comparing with max_profit, and max_profit is updated.

When traversal is complete, return max_profit.

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        min_price = float("inf")
        max_profit = 0

        for price in prices:
            min_price = min(min_price, price)
            max_profit = max(max_profit, price - min_price)
        return max_profit

Copy the code