0

## 【小馬的LeetCode練功坊】121, 122, 123,188,309,714題- 最佳買賣股票的時機

(好像還有一個隱藏的假設: 在最後一天時你手上不能有股票)

1. 差分陣列，就是原陣列的兩兩項之間的差，比如說假設每天的股價是`[7,1,5,3,6,4]`
那麼差分陣列就是`[-6, 4, -2, 3, -2]`，直覺來看，差分陣列反映每天股票的漲跌情況，
比如說第一項「-6」表示第一天~第二天之間跌了6塊，第二項「4」表示第二天~第三天之間漲了4塊
2. 動態規劃經典題: 最大子陣列之和，原則上這系列的題目就是對差分陣列去求最大子陣列之和的各種變形

# 題目解析

``````class Solution:
def maxSubArray(self, nums: List[int]) -> int:
result = cur = nums[0]
for i in range(1, len(nums)):
cur = max(cur + nums[i], nums[i])
result = max(result, cur)
return result

def maxProfit(self, prices: List[int]) -> int:
if len(prices)<=1:
return 0
diff = [prices[i+1] - prices[i] for i in range(len(prices)-1)]
return max(0, self.maxSubArray(diff))
``````

``````class Solution:
def maxProfit(self, prices: List[int]) -> int:
diff = [prices[i+1] - prices[i] for i in range(len(prices)-1)]
return sum(filter(lambda x:x>0, diff))
``````

`cur[k][n]`表示最多可以有k個連續子陣列，一定要用第n個元素的最大和
`result[k][n]`表示最多可以有k個連續子陣列的最大總和
(當k=0時，表示不能做買賣股票，答案只能是0)

``````class Solution:
def max_twoSubArray(self, nums: List[int]) -> int:
result = [[0]*(len(nums)+2) for i in range(3)]
cur = [[0]*(len(nums)+2) for i in range(3)]
for k in range(1,3):
for n in range(len(nums)):
cur[k][n] = max(cur[k][n-1], result[k-1][n-2])+nums[n]
result[k][n] = max(result[k][n-1], cur[k][n])
return result[-1][-3]

def maxProfit(self, prices: List[int]) -> int:
if len(prices)<=1:
return 0
diff = [prices[i+1] - prices[i] for i in range(len(prices)-1)]
return self.max_twoSubArray(diff)
``````

`max_k_SubArray`用來做「最多K個連續子陣列之和」，

``````class Solution:
def max_k_SubArray(self, nums: List[int], K: int) -> int:
result = [[0]*(len(nums)+2) for i in range(K+1)]
cur = [[0]*(len(nums)+2) for i in range(K+1)]
for k in range(1, K+1):
for n in range(len(nums)):
cur[k][n] = max(cur[k][n-1], result[k-1][n-2])+nums[n]
result[k][n] = max(result[k][n-1], cur[k][n])
return result[-1][-3]

def maxProfit(self, k: int, prices: List[int]) -> int:
if len(prices)<=1 or k==0:
return 0
diff = [prices[i+1] - prices[i] for i in range(len(prices)-1)]
return sum(filter(lambda x:x>0, diff)) if k*2>=len(prices) else self.max_k_SubArray(diff,k)
``````

`cur[n]`表示一定要用第n個元素的最大和
`result[n]`表示不一定第n個元素的最大總和

``````class Solution:
def maxSubArray_withGap(self, nums: List[int]) -> int:
result = [0]*(len(nums)+2)
cur = [0]*(len(nums)+2)
for i in range(len(nums)):
cur[i] = max(cur[i-1], result[i-3]) + nums[i]
result[i] = max(result[i-1], cur[i])
return result[-3]

def maxProfit(self, prices: List[int]) -> int:
if len(prices) <= 1:
return 0
diff = [prices[i+1] - prices[i] for i in range(len(prices)-1)]
return self.maxSubArray_withGap(diff)
``````

• cash: 在這個時間點你沒有股票的最大獲益
• hold: 在這個時間點你持有股票的最大獲益

• 若原來沒有股票，今天也不買 (即原來cash的值)
• 若原來持有股票，今天賣股票 (hold + prices[i] - fee)

hold的值這樣更新:

• 若原來沒有股票，今天買股票 (cash - prices[i])
• 若原來持有股票，今天繼續持有 (即原來hold的值)
``````class Solution:
def maxProfit(self, prices: List[int], fee: int) -> int:
cash, hold = 0, -prices[0]
for i in range(1, len(prices)):
cash = max(cash, hold + prices[i] - fee)
hold = max(hold, cash - prices[i])
return cash
``````