題目描述

給定一個(gè)數(shù)組 prices ，它的第 i 個(gè)元素 prices[i] 表示一支給定股票第 i 天的價(jià)格。
你只能選擇 某一天 買入這只股票，并選擇在 未來的某一個(gè)不同的日子 賣出該股票。設(shè)計(jì)一個(gè)算法來計(jì)算你所能獲取的最大利潤。
返回你可以從這筆交易中獲取的最大利潤。如果你不能獲取任何利潤，返回 0 。

示例 1：
輸入：[7,1,5,3,6,4]
輸出：5
解釋：在第 2 天（股票價(jià)格 = 1）的時(shí)候買入，在第 5 天（股票價(jià)格 = 6）的時(shí)候賣出，最大利潤 = 6-1 = 5 。
注意利潤不能是 7-1 = 6, 因?yàn)橘u出價(jià)格需要大于買入價(jià)格；同時(shí)，你不能在買入前賣出股票。
示例 2：
輸入：prices = [7,6,4,3,1]
輸出：0
解釋：在這種情況下, 沒有交易完成, 所以最大利潤為 0。

Python

動(dòng)態(tài)規(guī)劃，maxp相當(dāng)于dp，保存最大的利潤
只要用一個(gè)變量記錄一個(gè)歷史最低價(jià)格 minprice，我們就可以假設(shè)自己的股票是在那天買的。那么我們?cè)诘?i 天賣出股票能得到的利潤就是 prices[i] - minprice。
因此，我們只需要遍歷價(jià)格數(shù)組一遍，記錄歷史最低點(diǎn)，然后在每一天考慮這么一個(gè)問題：如果我是在歷史最低點(diǎn)買進(jìn)的，那么我今天賣出能賺多少錢？當(dāng)考慮完所有天數(shù)之時(shí)，我們就得到了最好的答案

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        inf = int(1e9)# 1e9表示無窮大,記做一個(gè)大數(shù)
        minprice = inf
        maxprofit = 0 #保存當(dāng)前最大的利潤
        for price in prices:
            maxprofit = max(price - minprice, maxprofit)
            minprice = min(price, minprice)
        return maxprofit