題目描述
給定一個(gè)數(shù)組 prices 阳啥，它的第 i 個(gè)元素 prices[i] 表示一支給定股票第 i 天的價(jià)格。
你只能選擇 某一天 買(mǎi)入這只股票财喳，并選擇在 未來(lái)的某一個(gè)不同的日子 賣(mài)出該股票察迟。設(shè)計(jì)一個(gè)算法來(lái)計(jì)算你所能獲取的最大利潤(rùn)。
返回你可以從這筆交易中獲取的最大利潤(rùn)耳高。如果你不能獲取任何利潤(rùn)扎瓶，返回 0 。
示例 1：
輸入：[7,1,5,3,6,4]
輸出：5
解釋?zhuān)涸诘?2 天（股票價(jià)格 = 1）的時(shí)候買(mǎi)入泌枪，在第 5 天（股票價(jià)格 = 6）的時(shí)候賣(mài)出概荷，最大利潤(rùn) = 6-1 = 5 。
注意利潤(rùn)不能是 7-1 = 6, 因?yàn)橘u(mài)出價(jià)格需要大于買(mǎi)入價(jià)格碌燕；同時(shí)误证，你不能在買(mǎi)入前賣(mài)出股票。
示例 2：
輸入：prices = [7,6,4,3,1]
輸出：0
解釋?zhuān)涸谶@種情況下, 沒(méi)有交易完成, 所以最大利潤(rùn)為 0修壕。
Python
動(dòng)態(tài)規(guī)劃愈捅，maxp相當(dāng)于dp，保存最大的利潤(rùn)
只要用一個(gè)變量記錄一個(gè)歷史最低價(jià)格 minprice叠殷，我們就可以假設(shè)自己的股票是在那天買(mǎi)的改鲫。那么我們?cè)诘?i 天賣(mài)出股票能得到的利潤(rùn)就是 prices[i] - minprice。
因此林束，我們只需要遍歷價(jià)格數(shù)組一遍像棘，記錄歷史最低點(diǎn)，然后在每一天考慮這么一個(gè)問(wèn)題：如果我是在歷史最低點(diǎn)買(mǎi)進(jìn)的壶冒，那么我今天賣(mài)出能賺多少錢(qián)缕题？當(dāng)考慮完所有天數(shù)之時(shí)，我們就得到了最好的答案
class Solution:
def maxProfit(self, prices: List[int]) -> int:
inf = int(1e9)# 1e9表示無(wú)窮大,記做一個(gè)大數(shù)
minprice = inf
maxprofit = 0 #保存當(dāng)前最大的利潤(rùn)
for price in prices:
maxprofit = max(price - minprice, maxprofit)
minprice = min(price, minprice)
return maxprofit
