iT邦幫忙

0

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

感覺上leetcode的 Best Time to Buy and Sell Stock系列題還蠻實用的,
收錄在自己的題解裡,
這系列的題目假設說知道每天的股價,
要怎麼買賣股票才能得到最大的獲利,
並且假設你同時只能持有一張股票,
一定要先買股票才能賣股票,
不能買了股票當天就賣掉
(好像還有一個隱藏的假設: 在最後一天時你手上不能有股票)

在做這個系列的題目,
建議需要用兩個概念:

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

那我們開始吧~

題目解析

第一題: 121. Best Time to Buy and Sell Stock
題意: 最多只能買賣一次股票,求最大獲益?

解析: 既然只能買賣一次,表示對差分陣列求「最大連續子陣列之和」即可,
求「最大連續子陣列之和」就直接套用之前的程式,
之前那題「最大連續子陣列之和」必須至少包含一個元素

但是以此題來說,
如果發現股票只跌不漲,那我們就乾脆不做任何買賣,
答案至少為0

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))

第二題: 122. Best Time to Buy and Sell Stock
題意: 買賣股票的次數不限,求最大獲益?

解析: 「買賣股票的次數不限」是最簡單的變形,因為我們就股票漲的時候都賺到,在股票跳之前就先賣掉就行了
程式: 將差分陣列中所有正數加總

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))

第三題: 123. Best Time to Buy and Sell Stock III
題意: 最多只能買賣兩次股票,求最大獲益?

解析: 此題算是第一題的延伸,相當於求差分陣列的「最多兩個連續子陣列之和」
這邊我改用二維陣列來存結果,
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)

第四題: 188. Best Time to Buy and Sell Stock IV
題意: 最多只能買賣k次股票(k是給定的整數),求最大獲益?

解析: 本題需結合第二、三題的結果,
max_k_SubArray用來做「最多K個連續子陣列之和」,
但是當K很大、陣列長度很小的狀況,那其實就跟「買賣股票的次數不限」沒什麼兩樣,
因此需判斷當k*2>=len(prices)(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)

第五題: 309. Best Time to Buy and Sell Stock with Cooldown
題意: 買賣股票的次數不限,但是限制賣股票的隔天不能馬上買股票,求最大獲益?

解析: 這是「最大子陣列之和」的一種變形

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

估計有人會覺得奇怪:
為什麼cur[i] = max(cur[i-1], result[i-3]) + nums[i]
而不是cur[i] = max(cur[i-1], result[i-2]) + nums[i]?
直覺上「隔天不能馬上買股票」好像間隔一格就行了

因為在差分陣列間隔兩格(也就是index會差3)才表示「限制賣股票的隔天不能馬上買股票」。

舉例來說: 原陣列 = [1,2,3,0,2],差分陣列 = [1,1,-3,2]
取差分陣列[1],[2]的總和是可以的,
但取[1,1],[2]不行,
因為這樣表示第三天賣了股票,第四天又馬上買股票,
因此差分陣列需要間隔兩格才對

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)

第六題: 714. Best Time to Buy and Sell Stock with Transaction Fee
題意: 買賣股票的次數不限,但是每次買賣股票必須付固定手續費,求最大獲益?

解析: 我發現這一題跟前面幾題的思路不太一樣,也不好想,
不確定有沒有辦法有差分陣列來做,
看了解答才知道怎麼解

解答用了兩個變數:

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

第一天的hold是-prices[0],因為股票要賣掉才會有賺,
還沒賣掉之前現金還沒收回來

之後每到新的一天,cash的值這樣更新:

  • 若原來沒有股票,今天也不買 (即原來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

尚未有邦友留言

立即登入留言