Algorithm

Leetcode: Stock Transaction Collections

Posted by keys961 on April 22, 2020

1. 问题

Leetcode上有一个股票交易题集，包含：

  • 121：买卖股票的最佳时机（最多一次交易）
  • 122：买卖股票的最佳时机（可无限次交易）
  • 123：买卖股票的最佳时机（最多两次交易）
  • 188：买卖股票的最佳时机（给定最大次数交易）
  • 309：最佳买卖股票时机含冷冻期（可无限次交易，冷冻期一天）
  • 714：买卖股票的最佳时机含手续费（可无限次交易，卖出交手续费）

注意：一天只能买或卖一次，当天买了或卖了之后，当天不能其它操作

这些题目都可以用动态规划解决。

2. 解决思路

这里定义dp(i, j, 0 or 1)，代表：到第i天，最多交易j次，当前持有/未持有股票时，自己现金的净值。所以，很明显有：

  1. 当第i天持有股票时，dp(i, j, 1)取下面两值的最大值
  • dp(i - 1, j, 1)：前一天已持有股票，今天不操作
  • dp(i - 1, j - 1, 0) - price[i]：前一天没持有股票，今天买入
  1. 当第i天没持有股票时，dp(i, j, 0)取下面两值的最大值
    • dp(i - 1, j, 0)：前一天没持有股票，今天不操作
    • dp(i - 1, j, 1) + price[i]：前一天持有股票，今天卖出（注意这里取的是j，因为卖出和买入视作同一个交易）

初始化时，有：

  • dp(-1, j, 1) = -inf：初始时不可能持有股票，故标为-inf
  • dp(-1, j, 0) = 0：初始时不持有股票，净值为0

根据上面的推导，可以完全解决第1节中的六个问题。

2.1. 买卖股票的最佳时机（最多一次交易）

这里j最大只能为1，所以转移方程就变成：

  • dp(i, 1, 1) = max(dp(i - 1, 1, 1), dp(i - 1, 0, 0) - price[i]) = max(dp(i - 1, 1, 1), -price[i])

  • dp(i, 1, 0) = max(dp(i - 1, 1, 0), dp(i - 1, 1, 1) + price[i])

可见j都是1，所以该维度可以省略，直接变为：

  • dp(i, 1) = max(dp(i - 1, 1), -price[i])

  • dp(i, 0) = max(dp(i - 1, 0), dp(i - 1, 1) + price[i])

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
    public int maxProfit(int[] prices) {
        int[][] dp = new int[prices.length + 1][2];
        dp[0][1] = Integer.MIN_VALUE;

        for(int i = 1; i <= prices.length; i++) {
            dp[i][1] = Math.max(dp[i - 1][1], -prices[i - 1]);
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i - 1]);
        }
        return dp[prices.length][0];
    }
}

不过上面的问题，可以这么解：

  • 将prices数组转成diffs数组，表示两天股价差
  • 获取diffs数组的子数组的和最大值

2.2. 买卖股票的最佳时机（可无限次交易）

由于j可为正无穷，所以可以认为j与j - 1一样，所以转移方程就变成：

  • dp(i, j, 1) = max(dp(i - 1, j, 1), dp(i - 1, j - 1, 0) - price[i]) = max(dp(i - 1, j, 1), dp(i - 1, j, 0) - price[i])

  • dp(i, j, 0) = max(dp(i - 1, j, 0), dp(i - 1, j, 1) + price[i])

因此j这个维度也可以忽略，所以有：

  • dp(i, 1) = max(dp(i - 1, 1), dp(i - 1, 0) - price[i])

  • dp(i, 0) = max(dp(i - 1, 0), dp(i - 1, 1) + price[i])

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
    public int maxProfit(int[] prices) {
        int[][] dp = new int[prices.length + 1][2];
        dp[0][1] = Integer.MIN_VALUE;

        for(int i = 1; i <= prices.length; i++) {
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i - 1]);
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i - 1]);
        }
        return dp[prices.length][0];
    }
}

不过上面的问题，可以用贪婪解法：

  • 将prices数组转成diffs数组，表示两天股价差
  • 取所有的diffs的正数，求和

2.3. 买卖股票的最佳时机（最多两次交易）

直接套上面的转移方程即可，j最多为2。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
    public int maxProfit(int[] prices) {
        int[][][] dp = new int[prices.length + 1][2 + 1][2];
        for(int i = 0; i <= 2; i++) {
            dp[0][i][1] = Integer.MIN_VALUE;
        }

        for(int i = 1; i <= prices.length; i++) {
            for(int j = 1; j <= 2; j++) {
                dp[i][j][1] = Math.max(dp[i - 1][j][1],  dp[i - 1][j - 1][0] - prices[i - 1]);
                dp[i][j][0] = Math.max(dp[i - 1][j][0],  dp[i - 1][j][1] + prices[i - 1]);
            }
            
        }
        return dp[prices.length][2][0];
    }
}

不过上面的问题，可以用分治的解法：

  • 从左到右扫描，获得left数组，left[i]代表从第0到i天，交易1次的最大利润
    • 得到该数组通过2.1.得到
  • 从右到左扫描，获得right数组，right[i]代表从第i到最后一天，交易1次的最大利润
  • 最后的解就是ans = max(left[i] + right[i + 1])，其中1 <= i < prices.length

代码如下：

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

class Solution {
    public int maxProfit(int[] prices) {
        int[] left = calc(prices, true);
        int[] right = calc(prices, false);
        int max = 0;
        for(int i = 0; i < prices.length; i++) {
            max = Math.max(max, left[i] + right[i]);
        }
        return max;
    }
    
    private int[] calc(int[] prices, boolean left) {
        int[] arr = new int[prices.length];
        int best = 0;
        int sum = 0;
        if(left) {    
            for(int i = 1; i < prices.length; i++) {
                int diff = prices[i] - prices[i - 1];
                sum += diff;
                if(sum < 0) {
                    sum = 0;
                }
                best = Math.max(best, sum);
                arr[i] = best;
            }
        } else {
            for(int i = prices.length - 2; i >= 0; i--) {
                int diff = prices[i + 1] - prices[i];
                sum += diff;
                if(sum < 0) {
                    sum = 0;
                }
                best = Math.max(best, sum);
                arr[i] = best;
            }
        }
        return arr;       
    }
}

2.4. 买卖股票的最佳时机（给定最大次数交易）

完全就是第2节所述的状态转移公式。不过k过大时（超过prices长度的一半），即可转化为问题2.2.。

代码如下：

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

class Solution {
    public int maxProfit(int k, int[] prices) {
        if(k * 2 >= prices.length) {
            return maxProfitWithoutLimit(prices);
        }
        int[][][] dp = new int[prices.length + 1][k + 1][2];
        for(int i = 0; i <= k; i++) {
            dp[0][i][0] = 0;
            dp[0][i][1] = Integer.MIN_VALUE;
        }

        for(int i = 1; i <= prices.length; i++) {
            for(int j = 1; j <= k; j++) {
                // i-th day j-th trade with bond
                dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i - 1]);
                // i-th day j-th trade without bond
                dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i - 1]);
            }
        }

        return Math.max(dp[prices.length][k][0], dp[prices.length][k][1]);
    }
	
    // 2.2. Solution
    private int maxProfitWithoutLimit(int[] prices) {
        int ans = 0;
        for(int i = 1; i < prices.length; i++) {
            if(prices[i] > prices[i - 1]) {
                ans += prices[i] - prices[i - 1];
            }
        }
        return ans;
    }
}

2.5. 最佳买卖股票时机含冷冻期（可无限次交易，冷冻期一天）

只需要给第2节中提及的dp(i, j, 1)推导的第2个公式，将i-1改成i-2即可，即：

  1. 当第i天持有股票时，dp(i, j, 1)取下面两值的最大值

    • dp(i - 1, j, 1)：前一天已持有股票，今天不操作
    • dp(i - 2, j - 1, 0) - price[i]：前两天（因为冷冻期1天）没持有股票，今天买入

  2. 当第i天没持有股票时，dp(i, j, 0)取下面两值的最大值

    • dp(i - 1, j, 0)：前一天没持有股票，今天不操作
    • dp(i - 1, j, 1) + price[i]：前一天持有股票，今天卖出

由于可无限次交易，所以j的维度可以忽略。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
    public int maxProfit(int[] prices) {
        int[][] dp = new int[prices.length + 1][2];
        dp[0][1] = Integer.MIN_VALUE;

        for(int i = 1; i <= prices.length; i++) {
            // buy
            if(i - 2 < 0) {
                dp[i][1] = Math.max(dp[i - 1][1], -prices[i - 1]);
            } else {
                dp[i][1] = Math.max(dp[i - 1][1], dp[i - 2][0] - prices[i - 1]);
            }
            // sell
            dp[i][0] = Math.max(dp[i - 1][0], dp[i][1] + prices[i - 1]);
        }
        return dp[prices.length][0];
    }
}

2.6. 买卖股票的最佳时机含手续费（可无限次交易，卖出交手续费）

只需在卖出的时候，净资产值减去手续费fee即可。即：

  1. 当第i天持有股票时，dp(i, j, 1)取下面两值的最大值

    • dp(i - 1, j, 1)：前一天已持有股票，今天不操作
    • dp(i - 1, j - 1, 0) - price[i]：前一天没持有股票，今天买入

  2. 当第i天没持有股票时，dp(i, j, 0)取下面两值的最大值

    • dp(i - 1, j, 0)：前一天没持有股票，今天不操作
    • dp(i - 1, j, 1) + price[i] - fee：前一天持有股票，今天卖出，并减去手续费

由于可无限次交易，所以j的维度可以忽略。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
    public int maxProfit(int[] prices, int fee) {
        int[][] dp = new int[prices.length + 1][2];
        dp[0][1] = Integer.MIN_VALUE;
        for(int i = 1; i <= prices.length; i++) {
            // buy
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i - 1]);
            // sell, minus fee
            dp[i][0] = Math.max(dp[i - 1][0], dp[i][1] + prices[i - 1] - fee);
        }
        return dp[prices.length][0];
    }
}

3. 总结

总结就看第2节的推导公式，若题目有变，基本不会偏离这个推导公式。

CATALOG
    FEATURED TAGS
    Algorithm Java Network Distributed System Stream Processing Operating System Paper Linux Redis etcd Kubernetes C++