Buy and Sell Stock

Algorithms
dp, topic
Catalogue
  1. 1. 121. Best Time to Buy and Sell Stock
  2. 2. 122. Best Time to Buy and Sell Stock II
  3. 3. 122. Best Time to Buy and Sell Stock III
  4. 4. 188. Best Time to Buy and Sell Stock IV
  5. 5. 309. Best Time to Buy and Sell Stock with Cooldown
  6. 6. 714. Best Time to Buy and Sell Stock with Transaction Fee
  7. 7. Summary
    1. 7.1. States Definition
    2. 7.2. Induction Rule
    3. 7.3. Space Improving

121. Best Time to Buy and Sell Stock

  • Complete at most one transaction
  • We can get max profit when we buy on the lowest price and sell on the highest price!
  • we need to find $max(prices[j] - prices[i])$, for every i and j such that j > ij>i.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    class Solution(object):
        def maxProfit(self, prices):
            if not prices:
                return 0

            minp = prices[0]
            maxProfit = 0
            for i in xrange(1, len(prices)):
                minp = min(minp, prices[i])
                maxProfit = max(maxProfit, prices[i] - minp)
            return maxProfit

122. Best Time to Buy and Sell Stock II

  • Complete as many transactions as you like
  • Greedy Algorithms
1
2
3
4
5
6
7
class Solution(object):
    def maxProfit(self, prices):
        res = 0
        for i in xrange(1, len(prices)):
            if prices[i] > prices[i-1]:
                res += prices[i]-prices[i-1]
        return res

122. Best Time to Buy and Sell Stock III

  • Complete at most two transactions
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def maxProfit(self, prices):
        n = len(prices)
        if n <= 0: return 0

        left = [0] * n
        minp = prices[0]
        for i in xrange(1, len(prices)):
            minp = min(minp, prices[i])
            left[i] = max(left[i-1], prices[i] - minp)

        maxp = prices[-1]
        right = [0] * (n)
        res = 0
        for i in xrange(len(prices)-2, -1, -1):
            maxp = max(maxp, prices[i])
            right[i] = max(maxp - prices[i], right[i+1])
            res = max(res, right[i] + (left[i-1] if i > 1 else 0))
        return res

188. Best Time to Buy and Sell Stock IV

  • Complete at most k transactions
  • Watch Out: when k > n/2, you can use greedy algorithm from II
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def maxProfit(self, k, prices):
        if not prices or k == 0:
            return 0

        n = len(prices)
        if k > n // 2:
            return self.helper(prices)

        glob  = [[0] * (k+1) for _ in range(n)]
        local = [[0] * (k+1) for _ in range(n)]
        for i in range(1, n):
            diff = prices[i] - prices[i-1]
            for j in range(1, k+1):
                local[i][j] = max(glob[i-1][j-1], local[i-1][j]) + diff
                glob[i][j] = max(glob[i-1][j], local[i][j])
        return glob[-1][-1]


    def helper(self, prices):
        res = 0
        for i in range(1, len(prices)):
            res += max(0, prices[i] - prices[i-1])
        return res
  • Why do we need local and global two dp states?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def maxProfit(self, k, prices):
        if not prices or k == 0:
            return 0

        n = len(prices)
        if k > n // 2:
            return self.helper(prices)

        hold  = [[0] * (k+1) for _ in range(n)]
        unhold = [[0] * (k+1) for _ in range(n)]

        hold[0][0] = -prices[0]
        for i in range(1, n):
            hold[i][0] = max(hold[i-1][0], -prices[i])

        for i in range(k+1):
            hold[0][i] = -prices[0]

        for i in range(1, n):
            for j in range(1, k+1):
                hold[i][j] = max(hold[i-1][j], unhold[i-1][j]-prices[i])
                unhold[i][j] = max(unhold[i-1][j], hold[i-1][j-1]+prices[i])
        return unhold[-1][-1]

309. Best Time to Buy and Sell Stock with Cooldown

  • The natural states for this problem is the 3 possible transactions : buy, sell, rest. Here rest means no transaction on that day (aka cooldown).
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def maxProfit(self, prices):
        if not prices:
            return 0

        n = len(prices)
        buy = [0] * n
        sell = [0] * n
        buy[0] = -prices[0]
        for i in range(1, n):
            buy[i] = max(buy[i-1], (sell[i-2] if i > 1 else 0) - prices[i])
            sell[i] = max(sell[i-1], buy[i-1] + prices[i])
        return sell[-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def maxProfit(self, prices):
        if not prices:
            return 0

        n = len(prices)
        buy = -prices[0]
        prev_sell = sell = 0
        for i in range(1, n):
            prev_buy = buy
            buy = max(buy, prev_sell - prices[i])
            prev_sell = sell
            sell = max(sell, buy + prices[i])
        return sell

714. Best Time to Buy and Sell Stock with Transaction Fee

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def maxProfit(self, prices, fee):
        if not prices:
            return 0

        n = len(prices)
        sell = [0] * n
        buy = [0] * n
        buy[0] = -prices[0]
        for i in range(1, n):
            buy[i] = max(buy[i-1], sell[i-1]-prices[i])
            sell[i] = max(sell[i-1], buy[i-1]+prices[i]-fee)
        return sell[-1]

Summary

States Definition

  • Then the transaction sequences can end with any of these three states.
    For each of them we make an array, buy[n], sell[n] and rest[n].
  1. buy[i] means before day i what is the maxProfit for any sequence end with buy.
  2. sell[i] means before day i what is the maxProfit for any sequence end with sell.
  3. rest[i] means before day i what is the maxProfit for any sequence end with rest.
  • Hold and Unhold
  1. hold[i] means before day i what is the maxProfit for any sequence end with holding stock.
  2. unhold[i] means before day i what is the matProfit for any sequence end with unholding stock.

Induction Rule

TODO

Space Improving

TODO

Share