Best Time to Buy and Sell Stock

Posted on Edited on In Views: 36

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: i.e. you may buy at most k times and sell at most k times.

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

Intro

我们直接看最抽象的188. Best Time to Buy and Sell Stock IV, 其它股票问题都是它的具体形式.

188的题面就是上文.

Example 1:

1
2
3
Input: k = 2, prices = [2,4,1]
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.

Example 2:

1
2
3
Input: k = 2, prices = [3,2,6,5,0,3]
Output: 7
Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4. Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.

在同一天买卖同一支股票并不影响结果.

Solution

使用动态规划(DP).

  • DP数组dp[i][j][k]: 在天数为[0,1,2,...,i]的这段时间内, 当天的持有股票状态为{j}, 且最大交易数为{k}的情况下, 能达到的最大利润.
    • i = {0, 1, ..., prices.length-1}
    • j = {0,1}, 表达当天是否持有股票. 0: 不持有, 1: 持有.
    • k = {0,1,2, ...., K}: 最大交易次数, 共有K+1种情况. 题目给定的最大交易次数为K.
  • 返回值: 如果利润要最大, 最后一天结束时手里就不能有股票, 因此最后一天的j = 0. 因此返回值为dp[prices.length-1, 0, K].
  • DP函数void buildDP(Integer[][][] memo, int i, int k, int[] prices): 对dp[i][0][k], dp[i][1][k]进行赋值.
    • 你也可以把函数定义为void buildDP(Integer[][][] dp, int i, int j, int k, int[] prices), 每次调用都对dp[i][j][k]进行赋值. 这样只会使解法更复杂, 因为j只有0和1两种情况, 直接放在一起处理更方便.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int maxProfit(int K, int[] prices) {

    /**
     * dp[i][j][k]: 在天数为[0,1,2,...,i]的这段时间内, 当天的持有股票状态为{j}, 且最大交易数为{k}的情况下, 能达到的最大利润.
     * i = {0, 1, ..., prices.length-1}
     * j = {0,1}, 表达当天是否持有股票. 0: 不持有, 1: 持有.
     * k = {0,1,2, ...., K}: 最大交易次数, 共有K+1种情况.
     */
    Integer[][][] dp = new Integer[prices.length][2][K+1];
    dp(dp, prices.length-1, K, prices);//得到dp[prices.length-1][0][K], 即在最后一天(i=len-1)且当天不持有股票的(j=0)情况下能达到的最大利润.
    int max = dp[prices.length-1][0][K];
    return max;
}

/**
 * 使用动态规划.
 * 对dp[i][0][k], dp[i][1][k]进行赋值.
 */
private void dp(Integer[][][] dp, int i, int k, int[] prices)
{
  //...
}

DP process

每次状态转移有三种选择:

  • sell: 卖出当天手中的股票. dp[i][0][k] = dp[i-1][0][k-1] + prices[i]
  • buy: 买下当天的股票. dp[i][1][k] = dp[i-1][0][k-1] - prices[i]
  • rest: 不进行任何操作. dp[i][j][k] = dp[i-1][j][k-1]

事实上还可以有第四种操作: sell-buy, 即在当天进行相同次数的sell和buy, 得到的总利润不变, 但消耗最大交易次数. 即:

1
dp[i][j][k] = dp[i-1][j][k-1]

然而, 由于dp[i][j][k-1](sell-buy) <= dp[i][j][k](rest)恒成立, 所以sell的利润永远不能超过rest. 所以这种情况被排除.

Note: Change of k

注意k的变化:

这类题目规定: (sell, buy)等于一次交易. 只有buy占用交易次数, sell和rest均不占用.

例如[0,1,2]这三天的最大交易次数为2, 那么可以进行2次buy + 2次sell.

假设[0,1,2,3]的最大交易次数为k:

  1. 如果在第i=3天sell, 那么[0,1,2]的最大交易次数依然为k次, 因为第i=3天进行的sell不占用交易次数.

  2. 如果在第i=3天buy,那么[0,1,2]的最大交易次数就变成k-1次, 因为第i=3天的buy会占用一个交易次数.

Special Case: i = 0

在第0天时:

  • 在当天不持有股票(i=0)的情况下, 无论k为多少, 利润都为0:

    1
    dp[i][0][k] = 0;

  • 在当天持有股票(j=1)的情况下:

    • 如果当天的最大交易次数k为正数, 那么可以通过q次buy和q-1次sell来使得当天能够持有股票, q <= k. 因此:

      1
      dp[i][1][k] = -prices[i].

    • 如果当天的最大交易次数k=0, 那么说明在当天不允许任何交易, 因此当天不可能持有股票, 这与j=1矛盾, 因此令利润为null:

      1
      dp[i][1][k] = null;

Special Case: k = 0

如果第i天(i>0)的k=0, 说明[0,1,2,...,i]这段时间内不允许发生任何交易, 因此不能发生任何一次buy(因此也就不能有任何的sell).

  • 如果j=0, 则[0,1,2,...,i]的最大利润就是[0,1,2,...,i-1]的最大利润, 因为不可能发生sell.

    1
    dp[i][0][k] = dp[i-1][0][k];

    dp[i][0][0] 会一直递归到dp[0][0][0] = 0.

  • 如果j=1, 说明第i天当天持有了股票, 这和"这段时间内不能buy"是矛盾的.

    1
    dp[i][1][k] = null

Don't Have Stock Today(j=0)

如果第i天(i>0)天k>0, 那么在此期间可以发生buy和sell.

如果当天不持有股票(j=0), 有两种情况:

  1. 昨天没有持有, 且今天rest. rest不消耗交易次数, 所以昨天的k和今天的一样.

    解释: 我昨天就没有持有，且截至昨天最大交易次数限制为 k；然后我今天选择 rest，所以我今天还是没有持有，最大交易次数限制依然为 k。

  2. 昨天持有了股票, 今天sell了. sell不消耗交易次数, 所以昨天的k和今天的一样.

    解释: 我昨天持有股票, 且截至昨天最大交易次数限制为 k; 但是今天我 sell 了, 所以我今天没有持有股票了, 最大交易次数限制依然为 k.

1
2
dp[i][0][k] = max(dp[i-1][0][k], dp[i-1][1][k] + prices[i])
              max( 今天选择rest,        今天选择 sell       )

Have Stock Today(j=1)

如果第i天(i>0)天k>0, 那么在此期间可以发生buy和sell.

如果当天持有股票(j=0), 有两种情况:

  1. 昨天持有了股票, 且今天rest. sell不消耗交易次数, 所以昨天的k和今天的一样.

    解释: 我昨天就持有着股票, 且截至昨天最大交易次数限制为 k; 然后今天选择 rest，所以我今天还持有着股票，最大交易次数限制依然为 k.

  2. 昨天没有持有, 今天buy了. buy消耗交易次数, 所以昨天的k比今天的少一次(截至今天最多交易k次, 今天要buy, 消耗一次, 所以截至昨天就只能最多交易k-1次).

    解释: 我昨天本没有持有, 且截至昨天最大交易次数限制为 k - 1; 但今天我选择 buy, 所以今天我就持有股票了, 最大交易次数限制为 k.

1
2
dp[i][1][k] = max(dp[i-1][1][k], dp[i-1][0][k-1] - prices[i])
              max( 今天选择rest),         今天选择 buy         )

Code

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
/**
 * 188. Best Time to Buy and Sell Stock IV
 */
public class Solution188 {
    public int maxProfit(int K, int[] prices) {

        /**
         * dp[i][j][k]: 在天数为[0,1,2,...,i]的这段时间内, 当天的持有股票状态为{j}, 且最大交易数为{k}的情况下, 能达到的最大利润.
         * i = {0, 1, ..., prices.length-1}
         * j = {0,1}, 表达当天是否持有股票. 0: 不持有, 1: 持有.
         * k = {0,1,2, ...., K}: 最大交易次数, 共有K+1种情况.
         */
        Integer[][][] dp = new Integer[prices.length][2][K+1];
        buildDP(dp, prices.length-1, K, prices);//得到memo[prices.length-1][0][K], 即在最后一天(i=len-1)且当天不持有股票的(j=0)情况下能达到的最大利润.
        int max = dp[prices.length-1][0][K];
        return max;
    }

    /**
     * 使用动态规划.
     * 对memo[i][0][k], memo[i][1][k]进行赋值.
     */
    private void buildDP(Integer[][][] memo, int i, int k, int[] prices)
    {
        if( i < 0 || k < 0 ) return; //k is the number of max transaction, k can't be negative. So is i.
        if(memo[i][0][k] != null ) return;

        if(i == 0)
        {

            //在当天不持有股票(i=0)的情况下, 无论k为多少, 利润都为0.
            memo[i][0][k] = 0;

            //
            //如果当天的最大交易次数k>0, 那么可以通过q次buy和q-1次sell来使得当天能够持有股票, q <= k. memo[i][1][k] = -prices[i].
            //如果当天的最大交易次数k=0, 那么说明在当天不允许任何交易, 因此当天不可能持有股票. memo[i][1][k] = null;
            memo[i][1][k] = k>0 ? -prices[i]: null;

        }
        else
        {
            //DP, 得到第i-1天, 最大交易次数为k, k-1时的最大利润.
            buildDP(memo, i-1, k, prices);
            buildDP(memo, i-1, k-1, prices);

            if(k==0)
            {
                //如果第i天(i>0)的k=0, 说明[0,1,2,...,i]这段时间内不允许发生任何交易, 因此不能发生任何一次buy(因此也就不能有任何的sell).
                //如果j=0, 则[0,1,2,...,i]的最大利润就是[0,1,2,...,i-1]的最大利润, 因为不可能发生sell. memo[i][0][0] 会一直递归到memo[0][0][0] = 0.
                //如果j=1, 说明第i天当天持有了股票, 由于这段时间内不可能发生buy, 所以这种情况不可能发生. memo[i][1][k] = null
                memo[i][0][k] = memo[i-1][0][k];
                memo[i][1][k] = null;
            }
            else
            {
                //如果第i天(i>0)天k>0, 那么在此期间可以发生buy和sell.

                //如果当天不持有股票(j=0), 有两种情况:
                // 1. 昨天没有持有, 且今天rest. rest不消耗交易次数, 所以昨天的k和今天的一样, 因此求memo[i-1][0][k]
                // 2. 昨天持有了股票, 今天sell了. sell不消耗交易次数, 所以昨天的k和今天的一样, 因此求memo[i-1][1][k] + prices[i]
                memo[i][0][k] = Math.max(memo[i-1][0][k], memo[i-1][1][k] + prices[i]);

                //如果当天持有股票(j=0), 有两种情况:
                // 1. 昨天持有了股票, 且今天rest. sell不消耗交易次数, 所以昨天的k和今天的一样, 因此求memo[i-1][1][k]
                // 2. 昨天没有持有, 今天buy了. buy消耗交易次数, 所以昨天的k比今天的少一次(截至今天最多交易k次, 今天要buy, 消耗一次, 所以截至昨天就只能最多交易k-1次), 因此求memo[i-1][0][k]
                memo[i][1][k] = Math.max(memo[i-1][1][k], memo[i-1][0][k-1] - prices[i]);
            }
        }
        return;
    }
}