The best time to buy and sell stocks to get the maximum return

The best time to buy and sell stocks is to get the maximum return

Given an array prices , It's the first i Elements prices[i] Represents the number of shares in a given stock i Sky price .

You can only choose One day Buy this stock , And choose A different day in the future Sell the stock . Design an algorithm to calculate the maximum profit you can get .

Return the maximum profit you can make from the deal . If you can't make any profit , return 0

Their thinking

（1） Use of violence , Find the two elements in the array with the largest difference , The difference is the maximum return , At the same time, the selling price is greater than the buying price , namely The first j The first element is greater than the i Elements ,j>i.

def maxProfit(prices):
    result = 0

    for i in range(len(prices)):
        for j in range(i + 1, len(prices)):
            result = max(result, prices[j] - prices[i])
    return result

But the time complexity of violence law is relatively high , When the array is very large .
（2） Dynamic planning ideas , Find the lowest value , Calculate the difference between other elements and the lowest value , Dynamically update the minimum number , Calculate the maximum difference .

def maxProfit(prices):
	minprice = int(1e9)
    profit = 0
    for price in prices:
        profit = max(price - minprice, profit)
        minprice = min(price, minprice)
    return profit

This method loops through the array once , Low time complexity .
Record the process of question brushing , insist , insist , insist .