題目
給定一個(gè)數(shù)組 prices ，它的第 i 個(gè)元素 prices[i] 表示一支給定股票第 i 天的價(jià)格。你只能選擇某一天買入這只股票，并選擇在未來的某一個(gè)不同的日子賣出該股票。設(shè)計(jì)一個(gè)算法來計(jì)算你所能獲取的最大利潤。返回你可以從這筆交易中獲取的最大利潤。如果你不能獲取任何利潤，返回 0 。
例：
輸入：[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í)，你不能在買入前賣出股票。
方法：暴力解法
計(jì)算每天若要選擇賣出的話的最大利潤，通過兩個(gè)循環(huán)實(shí)現(xiàn)
class Solution(object):
def maxProfit(self, prices):
result = 0
for i in range(1, len(prices)):
for j in range(i):
if prices[i] - prices[j] > result:
result = prices[i] - prices[j]
return result
※ 超出時(shí)間限制
方法：貪心算法
- result 表示當(dāng)前利潤的最大值，low 表示當(dāng)前遇到的價(jià)格最小值
- 通過循環(huán)實(shí)現(xiàn)對兩個(gè)參數(shù)的記錄
class Solution(object):
def maxProfit(self, prices):
result = 0
low = float('inf')
for i in range(len(prices)):
low = min(low, prices[i])
result = max(result, prices[i] - low)
return result
方法：動(dòng)態(tài)規(guī)劃
- dp[i][0] 表示第 i 天持有股票所擁有的最多現(xiàn)金（負(fù)數(shù)），dp[i][1] 表示第 i 天不持有股票所擁有的最多現(xiàn)金
- 初始化。dp[0][0] 即第一天持有股票所擁有的最多現(xiàn)金，即第一天買入股票，那么此時(shí)應(yīng)賦值 -prices[0]；dp[0][1]即第一天不持有股票所擁有的最多現(xiàn)金，即第一天不買入股票，那么此時(shí)賦值 0
- 循環(huán)記錄。dp[i][0] 有兩種可能性：第 i-1 天就持有股票 dp[i-1][0]，第 i-1 天并未持有股票但在第 i 天買入股票 -prices[i]，取這兩種可能的較大值。dp[i][1] 有兩種可能：第 i-1 天就未持有股票 dp[i-1][1]，第 i-1 天持有股票但在第 i 天賣出股票 prices[i] + dp[i-1][0]，取這兩種可能的較大值
class Solution(object):
def maxProfit(self, prices):
dp = [[0] * 2 for row in range(len(prices))]
dp[0][0], dp[0][1] = -prices[0], 0
for i in range(1, len(prices)):
dp[i][0] = max(dp[i-1][0], -prices[i])
dp[i][1] = max(dp[i-1][1], prices[i] + dp[i-1][0])
return dp[-1][1]
