[LeetCode] #188. Best Time to Buy and Sell Stock IV

-

題目

You are given an integer array prices where prices[i] is the price of a given stock on the ith day, and an integer k.

Find the maximum profit you can achieve. You may complete at most k transactions.

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

直覺解

構想：

先找出所有可以低買高賣的時機，再從這些時機裡面挑出 k 個。挑選方式：while 迴圈，每圈會減少一個時機，減少方式有兩種，合併兩個相鄰的時機，或移除一個時機。

python 3 實作（失敗）：

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        profit = 0
        
        if len(prices) < 2 or k == 0:
            return profit
        
        # find all best time to buy and sell stock
        start = 0
        intervals = []
        while start < len(prices):
            interval = self.find_buy_sell_interval(start, prices)
            if interval['buy'] is None or interval['sell'] is None:
                break
            interval['subtotal'] = prices[interval['sell']] - prices[interval['buy']]
            intervals.append(interval)
            start = interval['sell'] + 1

        # pick k best time to buy and sell stock
        if not intervals:
            return profit

        while len(intervals) > k:
            # merge two intervals, or remove one interval
            merge_interval_index = 0
            merge_subtotal = prices[intervals[1]['sell']] - prices[intervals[0]['buy']]
            for i in range(2, len(intervals)):
                new_profit = prices[intervals[i]['sell']] - prices[intervals[i-1]['buy']]
                if new_profit > merge_subtotal:
                    merge_interval_index = i - 1
                    merge_subtotal = new_profit
            
            min_subtotal_interval_index = 0
            min_subtotal = intervals[0]['subtotal']
            for i in range(1, len(intervals)):
                if intervals[i]['subtotal'] < min_subtotal:
                    min_subtotal_interval_index = i
                    min_subtotal = intervals[i]['subtotal']
                
            if merge_subtotal > min_subtotal:
                left_interval = intervals.pop(merge_interval_index)
                right_interval = intervals.pop(merge_interval_index)
                intervals.append({'buy': left_interval['buy'], 'sell': right_interval['sell'], 'subtotal': merge_subtotal})
            else:
                del intervals[min_subtotal_interval_index]
            
        else:
            for interval in intervals:
                profit += interval['subtotal']
        
        return profit
        
    @staticmethod
    def find_buy_sell_interval(start, prices):
        buy_day = None
        sell_day = None

        # find buy day
        min_price_index = start
        start += 1
        while start < len(prices):
            if prices[start] <= prices[min_price_index]: 
                min_price_index = start
            else:
                buy_day = min_price_index
                break
            start += 1

        #find sell day
        sell_day = start
        while start < len(prices):
            if prices[start] >= prices[sell_day]:
                sell_day = start
            else:
                break
            start += 1

        return {'buy': buy_day, 'sell': sell_day}

Submission Detail

Wrong Answer

Input: 2, [1,2,4,2,5,7,2,4,9,0]

Output: 10

Expected: 13

失敗原因

合併兩個相鄰的時機時，挑錯合併的對象。所有能低買高賣的時機為：

  1. price 1 時買，price 4 時賣，獲利 3

  2. price 2 時買，price 7 時賣，獲利 5

  3. price 2 時買，price 9 時賣，獲利 7

    4. 總獲利 15

合併兩個相鄰的時機時，我的程式碼把第 2、3 個時機合併了。因為 1、2 合併後變成 price 1 時買，price 7 時賣，獲利 6，而 2、3 合併後變成 price 2 時買，price 9 時賣，獲利 7。我的程式碼挑了能夠帶來最大獲利的那個組合去合併。最終結果變成：

  • price 1 時買，price 4 時賣，獲利 3

  • price 2 時買，price 9 時賣，獲利 7

    • 總獲利 10

但解答是把 1、2 合併，最終結果變成：

  • price 1 時買，price 7 時賣，獲利 6

  • price 2 時買，price 9 時賣，獲利 7

    • 總獲利 13

構想：

挑選合併的時機時，改成用「怎麼挑選，造成的損失比較小」為標準。

python 3 實作（失敗）：

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        profit = 0
        
        if len(prices) < 2 or k == 0:
            return profit
        
        # find all best time to buy and sell stock
        start = 0
        intervals = []
        while start < len(prices):
            interval = self.find_buy_sell_interval(start, prices)
            if interval['buy'] is None or interval['sell'] is None:
                break
            interval['subtotal'] = prices[interval['sell']] - prices[interval['buy']]
            intervals.append(interval)
            start = interval['sell'] + 1

        # pick k best time to buy and sell stock
        if not intervals:
            return profit

        while len(intervals) > k:
            # merge two intervals, or remove one interval
            merge_interval_index = 0
            merge_subtotal = prices[intervals[1]['sell']] - prices[intervals[0]['buy']]
            merge_loss = intervals[0]['subtotal'] + intervals[1]['subtotal'] - merge_subtotal
            for i in range(2, len(intervals)):
                new_subtotal = prices[intervals[i]['sell']] - prices[intervals[i-1]['buy']]
                new_loss = intervals[i - 1]['subtotal'] + intervals[i]['subtotal'] - new_subtotal
                
                if new_loss < merge_loss:
                    merge_interval_index = i - 1
                    merge_loss = new_loss
            
            min_subtotal_interval_index = 0
            loss_subtotal = intervals[0]['subtotal']
            for i in range(1, len(intervals)):
                if intervals[i]['subtotal'] < loss_subtotal:
                    min_subtotal_interval_index = i
                    loss_subtotal = intervals[i]['subtotal']
                
            if merge_loss < loss_subtotal:
                left_interval = intervals.pop(merge_interval_index)
                right_interval = intervals.pop(merge_interval_index)
                intervals.append({'buy': left_interval['buy'], 'sell': right_interval['sell'], 'subtotal': merge_subtotal})
            else:
                del intervals[min_subtotal_interval_index]
            
        else:
            for interval in intervals:
                profit += interval['subtotal']
        
        return profit
        
    @staticmethod
    def find_buy_sell_interval(start, prices):
        buy_day = None
        sell_day = None

        # find buy day
        min_price_index = start
        start += 1
        while start < len(prices):
            if prices[start] <= prices[min_price_index]: 
                min_price_index = start
            else:
                buy_day = min_price_index
                break
            start += 1

        #find sell day
        sell_day = start
        while start < len(prices):
            if prices[start] >= prices[sell_day]:
                sell_day = start
            else:
                break
            start += 1

        return {'buy': buy_day, 'sell': sell_day}

Submission Detail

Wrong Answer

Input: 2, [1,2,4,2,5,7,2,4,9,0,9]

Output: 16

Expected: 17

失敗原因

買賣股票的時機清單，我是有按照時間排序的。但我把 merge 後的時機加進去清單時，沒有留意擺放的順序，而是直接加在清單最尾巴。

一開始，挑出了四個低買高賣的時機，這時候清單有依照時間排序：

    prices = [1,2,4,2,5,7,2,4,9,0,9]

  1. price 1 時買，price 4 時賣，獲利 3

  2. price 2 時買，price 7 時賣，獲利 5

  3. price 2 時買，price 9 時賣，獲利 7

  4. price 0 時買，price 9 時賣，獲利 9

    5. 總獲利 24

因為 k 是 2，只能從中挑兩個時機。第一次挑選結果，是合併上述的 1、2，但合併後的結果，卻是排在時間順序的最後面：

    prices = [1,2,4,2,5,7,2,4,9,0,9]

  1. price 2時買，price 9 （day 9）時賣，獲利 7。

  2. price 0 時買，price 9（day 11）時賣，獲利 9。

  3. price 1（day 1）時買，price 7（day 6）時賣，獲利 6。日子都已經過到 day 11 了，這時候還想回去 day 1 買股票，然後在 day 6 時賣掉。

    4. 總獲利 22

因為 k 是 2，還需要再刪除一個時機。根據上述合併後的新清單，程式碼做了下列考量：

    prices = [1,2,4,2,5,7,2,4,9,0,9]

  • 合併 1、2，變成 price 2（day 7）時買，price 9（day 11）時賣，損失 9。

  • 合併 2、3，變成 price 0（day 10）時買，price 7（day 6）時賣，損失 8。

  • 刪除 3，放棄「price 1（day 1）時買，price 7（day 6）時賣」的機會，損失 6。

三種可能性中，刪除 3 的損失最小，所以決定刪除 3，所以最終的結果是：

    prices = [1,2,4,2,5,7,2,4,9,0,9]

  1. price 2 時買，price 9 時賣，獲利 7。賣出的時間是 day 9

  2. price 0 時買，price 9 時賣，獲利 9。賣出的時間是 day 11

    3. 總獲利 16

構想：

合併後的時機，放進清單時，要留意放置的位置。

python 3 實作（失敗）：

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        profit = 0
        
        if len(prices) < 2 or k == 0:
            return profit
        
        # find all best time to buy and sell stock
        start = 0
        intervals = []
        while start < len(prices):
            interval = self.find_buy_sell_interval(start, prices)
            if interval['buy'] is None or interval['sell'] is None:
                break
            interval['subtotal'] = prices[interval['sell']] - prices[interval['buy']]
            intervals.append(interval)
            start = interval['sell'] + 1

        # pick k best time to buy and sell stock
        if not intervals:
            return profit

        while len(intervals) > k:
            # merge two intervals, or remove one interval
            merge_interval_index = 0
            merge_subtotal = prices[intervals[1]['sell']] - prices[intervals[0]['buy']]
            merge_loss = intervals[0]['subtotal'] + intervals[1]['subtotal'] - merge_subtotal
            for i in range(2, len(intervals)):
                new_subtotal = prices[intervals[i]['sell']] - prices[intervals[i-1]['buy']]
                new_loss = intervals[i - 1]['subtotal'] + intervals[i]['subtotal'] - new_subtotal
                
                if new_loss < merge_loss:
                    merge_interval_index = i - 1
                    merge_loss = new_loss
            
            min_subtotal_interval_index = 0
            loss_subtotal = intervals[0]['subtotal']
            for i in range(1, len(intervals)):
                if intervals[i]['subtotal'] < loss_subtotal:
                    min_subtotal_interval_index = i
                    loss_subtotal = intervals[i]['subtotal']
                
            if merge_loss < loss_subtotal:
                left_interval = intervals.pop(merge_interval_index)
                right_interval = intervals.pop(merge_interval_index)
                intervals.insert(merge_interval_index, {'buy': left_interval['buy'], 'sell': right_interval['sell'], 'subtotal': merge_subtotal})
            else:
                del intervals[min_subtotal_interval_index]
            
        else:
            for interval in intervals:
                profit += interval['subtotal']
        
        return profit
        
    @staticmethod
    def find_buy_sell_interval(start, prices):
        buy_day = None
        sell_day = None

        # find buy day
        min_price_index = start
        start += 1
        while start < len(prices):
            if prices[start] <= prices[min_price_index]: 
                min_price_index = start
            else:
                buy_day = min_price_index
                break
            start += 1

        #find sell day
        sell_day = start
        while start < len(prices):
            if prices[start] >= prices[sell_day]:
                sell_day = start
            else:
                break
            start += 1

        return {'buy': buy_day, 'sell': sell_day}

Submission Detail

Wrong Answer

Input: 2, [6,5,4,8,6,8,7,8,9,4,5]

Output: 8

Expected: 7

失敗原因

買賣股票的時機是對的，但計算 profit 時算錯了。最後挑選出的時機如下：

    prices = [6,5,4,8,6,8,7,8,9,4,5]

  • price 4（day 3）時買，price 8（day 4）時賣，獲利 4。

  • price 6（day 5）時買，price 9（day 9）時賣，獲利 4。但正確的獲利值是 3。

算錯的原因，是因為我在挑選要合併哪兩個 interval 時，只顧著更新 merge_interval_index 和 merge_loss 的值，忘記更新 merge_subtotal，所以 merge_subtotal 一直維持是頭兩個 interval 合併後算出來的獲利值。

構想：

記得一併更新 merge_subtotal。

python 3 實作：

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        profit = 0
        
        if len(prices) < 2 or k == 0:
            return profit
        
        # find all best time to buy and sell stock
        start = 0
        intervals = []
        while start < len(prices):
            interval = self.find_buy_sell_interval(start, prices)
            if interval['buy'] is None or interval['sell'] is None:
                break
            interval['subtotal'] = prices[interval['sell']] - prices[interval['buy']]
            intervals.append(interval)
            start = interval['sell'] + 1

        # pick k best time to buy and sell stock
        if not intervals:
            return profit

        while len(intervals) > k:
            # merge two intervals, or remove one interval
            merge_interval_index = 0
            merge_subtotal = prices[intervals[1]['sell']] - prices[intervals[0]['buy']]
            merge_loss = intervals[0]['subtotal'] + intervals[1]['subtotal'] - merge_subtotal
            for i in range(2, len(intervals)):
                new_subtotal = prices[intervals[i]['sell']] - prices[intervals[i-1]['buy']]
                new_loss = intervals[i - 1]['subtotal'] + intervals[i]['subtotal'] - new_subtotal
                
                if new_loss < merge_loss:
                    merge_interval_index = i - 1
                    merge_subtotal = new_subtotal
                    merge_loss = new_loss
            
            min_subtotal_interval_index = 0
            loss_subtotal = intervals[0]['subtotal']
            for i in range(1, len(intervals)):
                if intervals[i]['subtotal'] < loss_subtotal:
                    min_subtotal_interval_index = i
                    loss_subtotal = intervals[i]['subtotal']
                
            if merge_loss < loss_subtotal:
                left_interval = intervals.pop(merge_interval_index)
                right_interval = intervals.pop(merge_interval_index)
                intervals.insert(merge_interval_index, {'buy': left_interval['buy'], 'sell': right_interval['sell'], 'subtotal': merge_subtotal})
            else:
                del intervals[min_subtotal_interval_index]
            
        else:
            for interval in intervals:
                profit += interval['subtotal']
        
        return profit
        
    @staticmethod
    def find_buy_sell_interval(start, prices):
        buy_day = None
        sell_day = None

        # find buy day
        min_price_index = start
        start += 1
        while start < len(prices):
            if prices[start] <= prices[min_price_index]: 
                min_price_index = start
            else:
                buy_day = min_price_index
                break
            start += 1

        #find sell day
        sell_day = start
        while start < len(prices):
            if prices[start] >= prices[sell_day]:
                sell_day = start
            else:
                break
            start += 1

        return {'buy': buy_day, 'sell': sell_day}

效能：

Runtime: 119 ms, faster than 38.45% of Python3 online submissions for Best Time to Buy and Sell Stock IV.
Memory Usage: 14.6 MB, less than 53.23% of Python3 online submissions for Best Time to Buy and Sell Stock IV.

研究別人的解

來源：Clean Python | 100% Speed

研究重點：想看更簡潔、更有效率的寫法。

別人的 python 3 實作（加上研究用的 print）：

class Solution:
    inf = float('inf')

    def cleaned(self, B):
        A, c = [B[0]], B[1]
        for i in range(1, len(B)-1):
            a, b, c = A[-1], c, B[i+1]
            if b == a or b == c or (a < b < c) or (a > b > c):
                continue
            A.append(b)
        A.append(B[-1])
        return A

    def maxProfit(self, k, prices):
        # For Problem # 123:
        #     -> Uncomment k = 2 here, and remove it from the function parameters
        # k = 2
        # -------------------- Initial Edge Cases --------------------
        if not k or len(prices) < 2:
            return 0
        #
        # Clean Prices
        prices = self.cleaned(prices)
        print('cleaned prices:', prices)
        #
        # Use all Profits
        profits = [prices[i]-prices[i-1]
                   for i in range(1, len(prices)) if prices[i] > prices[i-1]]
        print('all profit:', profits)
        if k >= len(profits):
            return sum(profits)
        #
        # -------------------- Main Code --------------------
        print('---- Main Code -----')
        B = [0]*k
        P = [self.inf]*k
        i = None
        for x in prices:
            P[0] = min(P[0], x)  # track min-buy point
            # track max. profit (buying now at lowest cost)
            B[0] = max(B[0], x-P[0])
            print('x:', x, 'P:', P, 'B:', B)
            print('--begin for--')
            for i in range(1, k):
                # Min Buy Point Subsidized by "i" Transactions
                P[i] = min(P[i], x - B[i-1])
                # Subsidized Profits (with current point)
                B[i] = max(B[i], x - P[i])
                print('i:', i, 'P:', P, 'B:', B)
                if B[i] == B[i-1]:
                    break  # We're just copying the previous transactions
            print('--end for--')
        return B[i] if i != None else B[0]

效能（沒有的 print 的版本）：

Runtime: 60 ms, faster than 98.30% of Python3 online submissions for Best Time to Buy and Sell Stock IV.
Memory Usage: 14.4 MB, less than 58.72% of Python3 online submissions for Best Time to Buy and Sell Stock IV.

研究感想

他的 cleaned 函式，是把所有最能低買高賣的時機都先篩選出來。例如：

    prices = [1,2,4,2,5,7,2,4,9,0,9]

  1. price 1 時買，price 4 時賣，獲利 3

  2. price 2 時買，price 7 時賣，獲利 5

  3. price 2 時買，price 9 時賣，獲利 7

  4. price 0 時買，price 9 時賣，獲利 9

所以 cleaned 完的結果是：prices = [1,4,2,7,2,9,0,9]，而 profits 就是 [3, 5, 7, 9]

跟我的 intervals 變數紀錄的事情類似，但是我的 intervals 紀錄得實在太囉唆，連買賣的時機是在 prices 的哪個 index 都要記。明明答案只在乎 profit，不在乎 index，但我還是把 index 的資訊存起來了。

在 P 和 B 的幫助下，迭代過一次 cleaned prices 就可以同時計算「最多只能做 1 次買賣的最大 profit」、「最多只能做 2 次買賣的最大 profit」、⋯⋯、「最多只能做 k 次買賣的最大 profit」，P 的設計真是太神乎其技了。

在「最多只能做 i 次買賣的限制下」（i 是 base 0），B[i] 是紀錄淨利，因為淨利越大越好，所以取最大值。P[i] 跟「在最低價時買股票」有關，但他不是紀錄股票價格，而是紀錄到目前為止買股票的成本（如果買賣股票有賺錢的話，成本可能會變成負數），因為成本越小越好，所以取最小值。這樣講還是挺抽象的，直接看例子比較容易懂：

input 是 k = 2, prices = [1, 2, 4, 2, 5, 7, 2, 4, 9, 0, 9] 時，印出來的東西（其中加入了我的筆記，筆記用粗體表示）：

cleaned prices: [1, 4, 2, 7, 2, 9, 0, 9]
all profit: [3, 5, 7, 9]

---- Main Code -----
cleaned prices: [1, 4, 2, 7, 2, 9, 0, 9]
x: 1 P: [1, inf] B: [0, 0]，
現在要決定，最多只能做 1 次買賣的話，買賣股票的時機
結果：在股票價格是 1 的時候買股票，現在還不能賣股票，淨利 0

    --begin for--
    i: 1 P: [1, 1] B: [0, 0]
    現在要決定，最多只能做 2 次買賣的話，2 次買賣股票的時機
    第 1 次買賣：在股票價格是 1 的時候買股票，現在還不能賣股票，淨利 0
    第 2 次買賣：還不能做第 2 次買賣
    --end for--

cleaned prices: [1, 4, 2, 7, 2, 9, 0, 9]
x: 4 P: [1, 1] B: [3, 0]
現在要決定，最多只能做 1 次買賣的話，買賣股票的時機
結果：在股票價格是 1 的時候買股票，在股票價格是 4 的時候賣股票，淨利 3

    --begin for--
    i: 1 P: [1, 1] B: [3, 0]
    現在要決定，最多只能做 2 次買賣的話，2 次買賣股票的時機
    第 1 次買賣：在股票價格是 1 的時候買股票，在股票價格是 4 的時候賣股票，淨利 3
    第 2 次買賣：還不能做第 2 次買賣
    --end for--

cleaned prices: [1, 4, 2, 7, 2, 9, 0, 9]
x: 2 P: [1, 1] B: [3, 3]
現在要決定，最多只能做 1 次買賣的話，買賣股票的時機
結果：在股票價格是 1 的時候買股票，在股票價格是 4 的時候賣股票，淨利 3

    --begin for--
    i: 1 P: [1, -1] B: [3, 3]
    現在要決定，最多只能做 2 次買賣的話，2 次買賣股票的時機
    P[1] 是 -1。若比照 B[0] 的時機交易後獲得淨利 3，然後在現在股票價格 2 的時候買股票，會倒賺 1 塊
    第 1 次買賣：在股票價格是 1 的時候買股票，在股票價格是 4 的時候賣股票，淨利 3
    第 2 次買賣：在股票價格是 2 的時候買股票，現在還不能賣股票
    --end for--

cleaned prices: [1, 4, 2, 7, 2, 9, 0, 9]
x: 7 P: [1, -1] B: [6, 3]
現在要決定，最多只能做 1 次買賣的話，買賣股票的時機
結果：在股票價格是 1 的時候買股票，在股票價格是 7 的時候賣股票，淨利 6

    --begin for--
    i: 1 P: [1, -1] B: [6, 8]
    現在要決定，最多只能做 2 次買賣的話，2 次買賣股票的時機
    P[1] 算出來是 -1：現在買股票太貴了，不買。所以維持原狀是 -1
    第 1 次買賣：在股票價格是 1 的時候買股票，在股票價格是 4 的時候賣股票，淨利 3
    第 2 次買賣：在股票價格是 2 的時候買股票，在股票價格是 7 的時候賣股票，淨利 5
	--end for--

cleaned prices: [1, 4, 2, 7, 2, 9, 0, 9]
x: 2 P: [1, -1] B: [6, 8]
現在要決定，最多只能做 1 次買賣的話，買賣股票的時機
結果：維持原狀，在股票價格是 1 的時候買股票，在股票價格是 7 的時候賣股票，淨利 6

    --begin for--
    i: 1 P: [1, -4] B: [6, 8]
    現在要決定，最多只能做 2 次買賣的話，2 次買賣股票的時機
    P[1] 是 -4：若比照 B[0] 的時機交易後獲得淨利 6，然後在現在股票價格 2 的時候買股票，會倒賺 4 塊
    已經準備要改成：第 1 次買賣：在股票價格是 1 的時候買股票，在股票價格是 7 的時候賣股票
                 第 2 次買賣：在股票價格是 2 的時候買股票，現在還不能賣股票
    
    但是，若比照上述方式進行買賣，現在卻還不能賣股票，淨利比不上原本的方式，所以先維持原狀：
    第 1 次買賣：在股票價格是 1 的時候買股票，在股票價格是 4 的時候賣股票，淨利 3
    第 2 次買賣：在股票價格是 2 的時候買股票，在股票價格是 7 的時候賣股票，淨利 5
    --end for--

cleaned prices: [1, 4, 2, 7, 2, 9, 0, 9]
x: 9 P: [1, -4] B: [8, 8]
現在要決定，最多只能做 1 次買賣的話，買賣股票的時機
結果：在股票價格是 1 的時候買股票，在股票價格是 9 的時候賣股票，淨利 8

    --begin for--
    i: 1 P: [1, -4] B: [8, 13]
    現在要決定，最多只能做 2 次買賣的話，2 次買賣股票的時機
    P[1]：現在買股票太貴了，不買。所以維持原狀是 -4
    第 1 次買賣：在股票價格是 1 的時候買股票，在股票價格是 7 的時候賣股票，淨利 6
    第 2 次買賣：在股票價格是 2 的時候買股票，在股票價格是 9 的時候賣股票，淨利 7
    --end for--

cleaned prices: [1, 4, 2, 7, 2, 9, 0, 9]
x: 0 P: [0, -4] B: [8, 13]
現在要決定，最多只能做 1 次買賣的話，買賣股票的時機
P[0] 是 0：發現更低的股票購買價格，先筆記下來。
如果日後找到淨利更好的賣股票時機，就會改成在股票價格是 0 的時候買股票。
結果：先維持原狀，在股票價格是 1 的時候買股票，在股票價格是 9 的時候賣股票，淨利 8

    --begin for--
    i: 1 P: [0, -8] B: [8, 13]
    現在要決定，最多只能做 2 次買賣的話，2 次買賣股票的時機
    P[1] 是 -8：若比照 B[0] 的時機交易後獲得淨利 8，然後在現在股票價格 0 的時候買股票，會倒賺 8 塊
    已經準備要改成：第 1 次買賣：在股票價格是 1 的時候買股票，在股票價格是 9 的時候賣股票
                 第 2 次買賣：在股票價格是 0 的時候買股票，現在還不能賣股票
    
    但是，若比照上述方式進行買賣，現在卻還不能賣股票，淨利比不上原本的方式，所以先維持原狀：
    第 1 次買賣：在股票價格是 1 的時候買股票，在股票價格是 7 的時候賣股票，淨利 6
    第 2 次買賣：在股票價格是 2 的時候買股票，在股票價格是 9 的時候賣股票，淨利 7
    --end for--

cleaned prices: [1, 4, 2, 7, 2, 9, 0, 9]
x: 9 P: [0, -8] B: [9, 13]
現在要決定，最多只能做 1 次買賣的話，買賣股票的時機
結果：在股票價格是 0 的時候買股票，在股票價格是 9 的時候賣股票，淨利 9

    --begin for--
    i: 1 P: [0, -8] B: [9, 17]
    現在要決定，最多只能做 2 次買賣的話，2 次買賣股票的時機
    P[1]：現在買股票太貴了，不買。所以維持原狀是 -8
    第 1 次買賣：在股票價格是 1 的時候買股票，在股票價格是 9 的時候賣股票，淨利 8
    第 2 次買賣：在股票價格是 0 的時候買股票，在股票價格是 9 的時候賣股票，淨利 9
    --end for--

Comments

Post a Comment

Popular posts from this blog

Alpha Camp 全端開發課程學習心得

-
我喜歡邏輯，在哲學系求學時期，我花最多時間的科目，是形式邏輯。但是我一直不明白這個我相對擅長的科目，到底能用在什麼地方。我的邏輯能力，並沒有好到足夠讓我走上學術研究的路，那麼，或許我可以試著寫程式？ 學生時期的我，自認沒有錢，但是有時間。捨不得花錢去上程式設計課程，寧願自己找資源學習。去上過一些免費的程式入門課程，c++ 和 python，對我而言不是很難，但是學完之後，我還是看不出來，要怎麼靠學到的東西解決生活中遇到的問題，漸漸地就沒有動力繼續學下去。 直到出社會，存了點錢，也漸漸體會到時間的重要，終於捨得花錢投資自己，到 Alpha Camp 上專業的課程，而不是無頭蒼蠅自己亂找一通，省下許多時間，也看到自己學的東西是真的能用的，讓我有動力繼續學下去。 我還記得學到串接 api 的時候，心裡真是太激動了。以前在學免費課程時，就隱約有種「我寫的程式，範圍只侷限在我的電腦上」的貧瘠感覺，而在知道了 api 後，發現「我寫的程式可以跟世界接上線了」，頓時覺得自己非常富有。不過，後來才知道，串別人的 api 服務通常是要付費的。 大概是受了形式邏輯的影響，我在學習程式語言時，總是試圖去辨認，哪些東西是比較基本的，基本的東西是透過什麼樣的規則組合出複雜的東西。例如，變數、array、for 迴圈和 function 是基本的東西，可以用這些基本的東西組合出 array 的 reduce 方法，像這樣： function mimicReduce(array, reducerFunction, initialValue) {     if (initialValue) {         let accumulator = initialValue         for (let i = 0; i < array.length; i++) {             accumulator = reducerFunction(accumulator, array[i])         }         return accumulator     } else {         let accumulator = array[0]         for (let i = 1; i < array.length; i
Read more

在 javascript 用 regular expression 為金額加上千位數分隔符號

-
 為了方便使用者快速判斷金額，所以想加上千位數分隔符號。例如： 3000 --> 3,000 3000000 --> 3,000,000 搜尋資料後，結論： 如果數字有小數點的話，可以用  const amount = '3000.00' amount.replace(/\B(?<!\.\d*)(?=(\d{3})+(?!\d))/g, ',') 參考資料： Javascript之數值千分位符號（Comma）的顯示 如果沒有小數點的話，可以用  const amount = '3000' amount.replace(/\B(?=(\d{3})+(?!\d))/g, ',') 參考資料： [Javascrpt]轉換數字成含千分位的文字   不過這個鬼畫符的語法我完全看不懂，查資料的時候一度不肯相信這是真正的程式碼呢⋯⋯因緣際會在讀書會中，得到 Helix 同學提示的關鍵字「 regular expression」，決定試著弄懂，「amount.replace(/\B(?=(\d{3})+(?!\d))/g, ',')」到底是什麼意思。 一、 String.prototype.replace() - MDN 範例：我不小心把 world 拼成 word，想要把句子裡所有的 word 都替換成  world。 const text = 'Hello word! Hello word!' console.log(text.replace('word', 'world')) 結果印出 Hello world! Hello word! 很不幸地，只有第一個錯字有替換，其他錯字都被放生了。如果想要替換全部的 word，就要這樣寫： const text = 'Hello word! Hello word!' console.log(text.replace( /word/ g , ' world '))
Read more

shop_platform - sqlalchemy.exc.TimeoutError

-
發生的問題 啟動伺服器後，第二十一次請求「需要查詢資料庫」的頁面時，會出現「sqlalchemy.exc.TimeoutError: QueuePool limit of size 10 overflow 10 reached, connection timed out, timeout 30.00 (Background on this error at: https://sqlalche.me/e/14/3o7r )」的錯誤訊息。如果請求是不需要查詢資料庫的（例如靜態檔案或前往登入頁面），就不會發生此錯誤。 把 size 和 overflow 設定成更小的數字，可以更快重現這個錯誤 。 感覺起來，就像查詢完資料庫以後，沒有把 connection 釋出一樣，導致「size + overflow」是多少，就只能查詢多少次資料庫。 發現瀏覽器每向伺服器請求一次「需要查詢資料庫」的頁面，在 MySQL Workbench 用 show PROCESSLIST; 指令的查詢結果就會多出一筆資料，筆數達到 size + overflow 時，若再次請求「需要查詢資料庫」的頁面，就會噴 QueuePool limit of size 10 overflow 10 reached 的錯誤。關閉伺服器時，那幾筆資料才會被刪除。 嘗試過但失敗的方法 app.run(debug=False) 自己註冊一個關閉 session 的函式 @app.teardown_appcontext # 改成 @app.teardown_request 也沒用 def teardown_db(exception): db.session.remove() # 改成 db.session.close() 也沒用 print('***** session.remove') # 這一行有印出來，所以此函式有被執行 把 FLASK_ENV=development 拿掉 ，於是 FLASK_ENV 變成預設的 production app.config["SQLALCHEMY_COMMIT_ON_TEARDOWN"] = True 終於成功的方法 第一種方法：用 Ap
Read more