題目描述
給定一個數(shù)組奖地，它的第 i 個元素是一支給定股票第 i 天的價格橄唬。
如果你最多只允許完成一筆交易（即買入和賣出一支股票），設(shè)計一個算法來計算你所能獲取的最大利潤参歹。
注意你不能在買入股票前賣出股票仰楚。
示例 1:
輸入: [7,1,5,3,6,4]
輸出: 5
解釋: 在第 2 天（股票價格 = 1）的時候買入，在第 5 天（股票價格 = 6）的時候賣出犬庇，最大利潤 = 6-1 = 5 僧界。
注意利潤不能是 7-1 = 6, 因為賣出價格需要大于買入價格。
示例 2:
輸入: [7,6,4,3,1]
輸出: 0
解釋: 在這種情況下, 沒有交易完成, 所以最大利潤為 0臭挽。
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有捂襟。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處欢峰。
解題思路
暴力法
雙層循環(huán)
高低谷想法
記錄最高值和最低值
我的直觀想法
這是我第一次嘗試寫出來的代碼
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if prices == []: return 0
# profit[][]
profit = [[0,0] for i in prices]
profit[0][0] = 0 # 假如上一次賣了能夠獲得的利潤 和 下面的 大者 葬荷，
# 本質(zhì)上profit[i][0]表示交易以今天結(jié)尾和不以今天結(jié)尾 哪個利潤大
profit[0][1] = 0 # 上次買直到今天獲得的利潤涨共，和0的 大者,如果是0，表示今天重新買入闯狱，
# 本質(zhì)上profit[i][1]表示的是以 i 為結(jié)尾的交易能夠獲得的利潤
for i in range(1,len(prices)):
profit[i][1] = max(profit[i-1][1]+prices[i]-prices[i-1],0)
profit[i][0] = max(profit[i-1][0],profit[i][1])
print(profit[i][0],profit[i][1])
return profit[-1][0]
但是如果看一下題解煞赢，會發(fā)現(xiàn)邏輯更強的推導(dǎo)。
以下為抄錄題解
這是一個最大連續(xù)子數(shù)組和的問題哄孤。有同學(xué)會問照筑，這是怎么看出來的，因為在數(shù)組中求兩點的差瘦陈，而兩點之差可以轉(zhuǎn)換成求和問題凝危。也許你還是一臉懵，這怎么想的到晨逝。如果你學(xué)過高等數(shù)學(xué)蛾默，對牛頓萊布尼茨公式有印象的話：
只不過支鸡，在我這里，F(xiàn)() 函數(shù)不是連續(xù)的趁窃，而是離散化的牧挣，aaa 和 bbb 表示數(shù)組的下標(biāo)。但是這不影響我們得出正確的結(jié)論醒陆。
總結(jié)下：區(qū)間和可以轉(zhuǎn)換成求差的問題瀑构，求差問題，也可以轉(zhuǎn)換成區(qū)間和的問題刨摩。
在上面的公式中寺晌，我們把 F()F()F() 表示的數(shù)組稱為前綴和。
最大連續(xù)子數(shù)組和可以使用動態(tài)規(guī)劃求解澡刹， dp[i]dp[i]dp[i] 表示以 iii 為結(jié)尾的最大連續(xù)子數(shù)組和呻征，遞推公式為：
版本一：
int maxProfit(vector<int>& prices) {
if (prices.size() <= 1) return 0;
vector<int> diff(prices.size() - 1);
for (int i = 0; i < prices.size() - 1; ++i) {
diff[i] = prices[i+1] - prices[i]; # 把序列轉(zhuǎn)換為差
}
vector<int> dp(diff.size());
dp[0] = max(0, diff[0]);
int profit = dp[0];
for (int i = 1; i < diff.size(); ++i) {
dp[i] = max(0, dp[i-1] + diff[i]);
profit = max(profit, dp[i]);
}
return profit;
}
作者：ivan_allen
鏈接：https://leetcode-cn.com/problems/two-sum/solution/121-mai-mai-gu-piao-de-zui-jia-shi-ji-dp-7-xing-ji/
來源：力扣（LeetCode）
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請聯(lián)系作者獲得授權(quán)罢浇，非商業(yè)轉(zhuǎn)載請注明出處怕犁。
版本二：
dp 數(shù)組可以被優(yōu)化掉
int maxProfit(vector<int>& prices) {
if (prices.size() <= 1) return 0;
vector<int> diff(prices.size() - 1);
for (int i = 0; i < prices.size() - 1; ++i) {
diff[i] = prices[i+1] - prices[i];
}
int last = 0;
int profit = last;
for (int i = 0; i < diff.size(); ++i) {
last = max(0, last + diff[i]);
profit = max(profit, last);
}
return profit;
}
作者：ivan_allen
鏈接：https://leetcode-cn.com/problems/two-sum/solution/121-mai-mai-gu-piao-de-zui-jia-shi-ji-dp-7-xing-ji/
來源：力扣（LeetCode）
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請聯(lián)系作者獲得授權(quán)己莺，非商業(yè)轉(zhuǎn)載請注明出處奏甫。
版本三：
diff 數(shù)組也可以被優(yōu)化掉
int maxProfit(vector<int>& prices) {
int last = 0, profit = 0;
for (int i = 0; i < (int)prices.size() - 1; ++i) {
last = max(0, last + prices[i+1] - prices[i]);
profit = max(profit, last);
}
return profit;
}
作者：ivan_allen
鏈接：https://leetcode-cn.com/problems/two-sum/solution/121-mai-mai-gu-piao-de-zui-jia-shi-ji-dp-7-xing-ji/
來源：力扣（LeetCode）
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請聯(lián)系作者獲得授權(quán)凌受，非商業(yè)轉(zhuǎn)載請注明出處阵子。
