Leetcode 3: stock

Posted on | | Visitors: | views

整理Leetcode上关于股票买卖的一组问题，本质是用贪心/动态求解全局最优

Buy&Sell 1 time

  • Problem: Say you have an array for which the ith element is the price of a given stock on day i. If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit. Note that you cannot sell a stock before you buy one.
  • Example: Input [7,1,5,3,6,4], output 5. Buy at 1 and sell at 6.
  • Link: https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
  • Answer:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    # Comment: 用一个变量记录已经查看过的价格中最低的点，称为买入价格；用另一个变量记录局部最优解，它的构成要么是当前价格 - 买入价格，要么就是之前的某个价格 - 买入价格。由此我们只需要遍历一遍数组即可。

    class Solution:
        def maxProfit(self, prices):
            if not prices:
                return 0
            minprice = prices[0]
            maxprofit = 0
            for price in prices[1:]:
                minprice = min(minprice, price)
                maxprofit = max(maxprofit, price - minprice)
            return maxprofit

Buy&Sell unlimited time

  • Problem: Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times). Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).
  • Example: Input [7,1,5,3,6,4], output: 7. 1st buy at 1 and sell at 5, then 2nd buy at 3 and sell at 6. Total we get 7.
  • Link: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/
  • Answer:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    # Comment: 本题与上一题的唯一区别就是可以买卖多次，所以局部最优解就从单次买卖的最优解变成累积和的最优解。我们不再需要记录买入价格，而是一旦当有盈利空间时，即当前价格 - 上一个价格 > 0，就实行买卖。

    class Solution:
        def maxProfit(self, prices):
            if not prices:
                return 0
            maxprofit = 0
            for i in range(1, len(prices)):
                if prices[i] > prices[i - 1]:
                    maxprofit += prices[i] - prices[i - 1]
            return maxprofit

Buy&Sell at most 2 time

  • Problem: Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete at most two transactions. Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).
  • Example: Input: [3,3,5,0,0,3,1,4], output: 6. 1st buy on first 0 and sell at 3, 2nd buy on 1 and sell on 4. If we can buy as many as we could, we would add one buy-sell at 3 and 5, then the output will be 8.
  • Link: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/
  • Answer:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    # Comment1: 因为买卖不能重叠（一定是买卖买卖），所以我们可以找到一个适当的点将数组分为两部分，在左右子数组各求出一次交易的最大值，即可得到本题的解。至于一次交易的最大值，就是和第一题的解法一致。
    # Comment2: 基于Comment1，最先想到的办法是扫描整个数组，然后分别计算扫描左右数组计算最大利润。这样做整个算法的复杂度是O(n^2)。
    # Comment3: 改进的办法是扫描两遍数组，并将每个切分点的利润保存下来。第一遍是从前往后扫描，这样就能把从第一天到第i天的最大利润记录下来。第二遍是从后往前扫描，这样用来记录第i天到最后一天的最大利润。最后取出两个组在同一个分界点时的最大利润和即可。

    class Solution:
        def maxProfit(self, prices):
            if len(prices) < 2:
                return 0

            pre_profit = [0]
            minprice = prices[0]
            maxprofit = 0
            for price in prices[1:]:
                minprice = min(minprice, price)
                maxprofit = max(maxprofit, price - minprice)
                pre_profit.append(maxprofit)

            pos_profit = [0]
            minprice = prices[-1]
            maxprofit = 0
            for price in prices[::-1][:-1]:
                minprice = max(minprice, price)
                maxprofit = max(maxprofit, minprice - price)
                pos_profit.insert(0, maxprofit)

            for i, profit in enumerate(pre_profit):
                maxprofit = max(maxprofit, profit + pos_profit[i])

            return maxprofit

    # Comment4: 思路是我们在第一次交易的基础上，考虑第二次交易。买卖买卖是不重叠的，因此第二次交易面临的世界必然是第一次交易决策完成后的世界。如果第一次交易没有进行，那么第二次交易就变为第一次交易；否则，我们可以将第一次交易的情况映射到股价上，这表示我们可以动用第一次交易的收益进行第二次交易，即在第二次交易前，股价会全面下跌第一次交易的收益。完成映射后，我们再进行第二次交易，此时的情况已经与第一次交易完全一致。

    class Solution:
        def maxProfit(self, prices):
            if len(prices) < 2:
                return 0       
                    
            minPrice1, minPrice2 = prices[0], prices[0]
            maxProfit1, maxProfit2 = 0, 0

            for price in prices[1:]:
                minPrice1 = min(price, minPrice1)
                maxProfit1 = max(maxProfit1, price - minPrice1)
                minPrice2 = min(minPrice2, price - maxProfit1)
                maxProfit2 = max(maxProfit2, price - minPrice2)
                    
            return maxProfit2

Buy&Sell at most k time

  • Problem: Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete at most k transactions. Note: You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
  • Example: Input: [3,2,6,5,0,3], k >= 2, output: 7. 1st buy at 2 and sell at 6, 2nd buy at 0 and sell at 3.
  • Link: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/
  • Answer:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    # Comment: 本题的关键是划定k的边界。对于一个长度为n的数组，买卖至多n // 2次。因此当k >= (n // 2)时，本题退化为k可为无限次的Case II，只需要用不断贪心求累积和即可；否则，与给定上限次数的CaseI、III一致。

    class Solution:
        def maxProfit(self, k, prices):
            if k == 0:
                return 0

            if len(prices) < 2:
                return 0

            if k >= len(prices) // 2:
                maxprofit = 0
                for i in range(1, len(prices)):
                    if prices[i] > prices[i - 1]:
                        maxprofit += prices[i] - prices[i - 1]
                return maxprofit
            else:
                minPrices = [prices[0]] * k
                maxProfits = [0] * k
                
                for price in prices[1:]:
                    minPrices[0] = min(price, minPrices[0])
                    maxProfits[0] = max(maxProfits[0], price - minPrices[0])
                    for i in range(1, k):
                        minPrices[i] = min(minPrices[i], price - maxProfits[i - 1])
                        maxProfits[i] = max(maxProfits[i], price - minPrices[i])
                
                return maxProfits[-1]

Buy&Sell unlimited time with cooldown limitation

  • Problem: Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions: You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again). After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)
  • Example: Input: [1,2,3,0,2], output: 3. 1st buy at 1 and sell at first 2, 2nd buy at 0 and sell at second 2. You cannot 1st buy&sell at (1, 3) and 2nd buy&sell at (0, 2), as we need cooldown
  • Link:
  • Answer:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    # Comment1: 本题与Case II类似，但实质上有着重大区别。因为我们无法连续买卖，所以不能继续用贪心求累积和的办法。这里改用动态规划。
    # Comment2: 首先我们明确在第i天，可做的操作有2种：买和卖。对于买，buy[i] = max(buy[i - 1], sell[i - 2] - prices[i])，即要不就是不买，要么就是用两天前卖出后的资金买入新的股票；对于卖，sell[i] = max(sell[i - 1], buy[i - 1] + prices[i])，要么就是不卖，要么就是把一天前买入的再卖出去。第一个式子已经包含了cooldown的逻辑，可见如果没有cooldown，那么直接用sell[i - 1]即可。

    class Solution:
        def maxProfit(self, prices):
            if len(prices) < 2 :
                return 0

            buy, sell, pre_buy, pre_sell = -prices[0], 0, 0, 0

            for price in prices:
                pre_buy = buy
                buy = max(pre_sell - price, pre_buy)
                pre_sell = sell
                sell = max(pre_buy + price, pre_sell)

            return sell


    # 下面这一段是用同样的思路解决Case II

    class Solution:
        def maxProfit(self, prices):
            if len(prices) < 2 :
                return 0

            buy, sell, pre_buy = -prices[0], 0, 0

            for price in prices:
                pre_buy = buy
                buy = max(sell - price, pre_buy)
                sell = max(pre_buy + price, sell)

            return sell

Buy&Sell unlimited time with fees

  • Problem: Your are given an array of integers prices, for which the i-th element is the price of a given stock on day i; and a non-negative integer fee representing a transaction fee. You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction. You may not buy more than 1 share of a stock at a time (ie. you must sell the stock share before you buy again.). Return the maximum profit you can make.
  • Example: Input: prices = [1, 3, 2, 8, 4, 9], fee = 2, output: 8. ((8 - 1) - 2) + ((9 - 4) - 2) = 8.
  • Link:
  • Answer:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    # Comment: 我们采用与上面一样的思路，只不过每次买入时需要扣除费用。

    class Solution:
        def maxProfit(self, prices, fee):
            if len(prices) < 2 :
                return 0

            buy, sell, pre_buy = -prices[0], 0, 0

            for price in prices:
                pre_buy = buy
                buy = max(sell - price, pre_buy)
                sell = max(pre_buy + price - fee, sell)

            return sell