每日一题 - 股票问题

买卖股票的最佳时机

题目信息

  • 题目描述：

    给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

    如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。

示例1:

1
2
3
4
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

示例2:

1
2
3
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

注意

1
1. 你不能在买入股票前卖出股票。

解题思路

本题难点

我们需要找出给定数组中两个数字之间的最大差值（即，最大利润）。此外，第二个数字（卖出价格）必须大于第一个数字（买入价格）。

形式上，对于每组 i 和 j（其中 j>i)，我们需要找出max(prices[j]−prices[i])。

具体思路

我们来假设自己来购买股票。随着时间的推移，每天我们都可以选择出售股票与否。那么，假设在第 i 天，如果我们要在今天卖股票，那么我们能赚多少钱呢？

显然，如果我们真的在买卖股票，我们肯定会想：如果我是在历史最低点买的股票就好了！太好了，在题目中，我们只要用一个变量记录一个历史最低价格 minprice，我们就可以假设自己的股票是在那天买的。那么我们在第 i 天卖出股票能得到的利润就是 prices[i] - minprice。

因此，我们只需要遍历价格数组一遍，记录历史最低点，然后在每一天考虑这么一个问题：如果我是在历史最低点买进的，那么我今天卖出能赚多少钱？当考虑完所有天数之时，我们就得到了最好的答案。

提示

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int maxProfit(int[] prices) {
        if(prices == null || prices.length == 0){
            return 0;
        }
        int profit = 0;
        int min = Integer.MAX_VALUE;
        for(int price : prices){
            if(price < min){
                min = price;
            }else{
                profit = Math.max(price - min,profit);
            }
        }
        return profit;
    }
}

复杂度分析：

  • 时间复杂度 O(N) ： 只需要遍历一次。
  • 空间复杂度 O(1) ： 只使用了常数个变量。

其他解答

解题思路

暴力法

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
    public int maxProfit(int prices[]) {
        int maxprofit = 0;
        for (int i = 0; i < prices.length - 1; i++) {
            for (int j = i + 1; j < prices.length; j++) {
                int profit = prices[j] - prices[i];
                if (profit > maxprofit) {
                    maxprofit = profit;
                }
            }
        }
        return maxprofit;
    }
}

复杂度分析：

  • 时间复杂度 O(N^2) ： 循环运行 n(n−1)/2 次
  • 空间复杂度 O(1) ： 只使用了常数个变量。

买卖股票的最佳时机 II

题目信息

  • 题目描述：

    给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

    设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

示例1:

1
2
3
4
输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

示例2:

1
2
3
4
5
输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

示例2:

1
2
3
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

注意

1
1.你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

解题思路

本题难点

考虑到「不能同时参与多笔交易」，因此每天交易结束后只可能存在手里有一支股票或者没有股票的状态。

具体思路

  1. 定义状态
    dp[i] [0]表示第 i 天交易完后手里没有股票的最大利润，dp[i] [1] 表示第 i 天交易完后手里持有一支股票的最大利润（i 从 0 开始）。

  2. 考虑 dp[i] [0] 的转移方程，如果这一天交易完后手里没有股票，那么可能的转移状态为前一天已经没有股票，即 dp[i−1] [0]，或者前一天结束的时候手里持有一支股票，即 dp[i−1] [1]，这时候我们要将其卖出，并获得 prices[i] 的收益。因此为了收益最大化，我们列出如下的转移方程：

    dp[i] [0]=max{dp[i−1] [0],dp[i−1] [1]+prices[i]}

  3. 再来考虑 dp[i] [1]，按照同样的方式考虑转移状态，那么可能的转移状态为前一天已经持有一支股票，即
    dp[i−1] [1]，或者前一天结束时还没有股票，即 dp[i−1] [0]，这时候我们要将其买入，并减少
    prices[i] 的收益。可以列出如下的转移方程：

    dp[i] [1]=max{dp[i−1] [1],dp[i−1] [0]−prices[i]}

提示

对于初始状态，根据状态定义我们可以知道第 0 天交易结束的时候 dp[0] [0]=0，dp[0] [1]=−prices[0]。

因此，我们只要从前往后依次计算状态即可。由于全部交易结束后，持有股票的收益一定低于不持有股票的收益，因此这时候 dp[n−1] [0] 的收益必然是大于 dp[n−1] [1] 的，最后的答案即为 dp[n−1] [0]。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0){
            return 0;
        }
        int n = prices.length;
        int[][] dp = new int[n][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for(int i = 1; i < n; i++){
            dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
            dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
        }
        return dp[n-1][0];
    }
}

注意到上面的状态转移方程中，每一天的状态只与前一天的状态有关，而与更早的状态都无关，因此我们不必存储这些无关的状态，只需要将 dp[i−1] [0] 和 dp[i−1] [1] 存放在两个变量中，通过它们计算出 dp[i] [0] 和 dp[i] [1] 并存回对应的变量，以便于第 i+1 天的状态转移即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int dp0 = 0, dp1 = -prices[0];
        for (int i = 1; i < n; ++i) {
            int newDp0 = Math.max(dp0, dp1 + prices[i]);
            int newDp1 = Math.max(dp1, dp0 - prices[i]);
            dp0 = newDp0;
            dp1 = newDp1;
        }
        return dp0;
    }
}

复杂度分析：

  • 时间复杂度 O(n) ： 其中 n 为数组的长度。一共有 2n 个状态，每次状态转移的时间复杂度为 O(1)，因此时间复杂度为 O(2n)=O(n)。
  • 空间复杂度 O(1) ： 我们需要开辟 O(n)空间存储动态规划中的所有状态。如果使用空间优化，空间复杂度可以优化至 O(1)。

其他优秀解答

解题思路

贪心算法的直觉：由于不限制交易次数，只要今天股价比昨天高，就交易。

代码

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

    public int maxProfit(int[] prices) {
        int len = prices.length;
        if (len < 2) {
            return 0;
        }

        int res = 0;
        for (int i = 1; i < len; i++) {
            int diff = prices[i] - prices[i - 1];
            if (diff > 0) {
                res += diff;
            }
        }
        return res;
    }
}

  • 时间复杂度O(n)：这里 N 表示股价数组的长度；

  • 空间复杂度O(1)：只使用了常数个变量。

买卖股票的最佳时机 III

题目信息

  • 题目描述：

    给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

    设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

示例1:

1
2
3
4
输入：prices = [3,3,5,0,0,3,1,4]
输出：6
解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
     随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。

示例2:

1
2
3
4
5
输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。   
     注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。   
     因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

示例3:

1
2
3
输入：prices = [7,6,4,3,1] 
输出：0 
解释：在这个情况下, 没有交易完成, 所以最大利润为 0。

注意

1
1.你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

解题思路

本题难点

限制了交易的次数，最多两次，同时要求收益最高

具体思路

由于我们最多可以完成两笔交易，因此在任意一天结束之后，我们会处于以下五个状态中的一种：

  • 未进行过任何操作；
  • 只进行过一次买操作；
  • 进行了一次买操作和一次卖操作，即完成了一笔交易；
  • 在完成了一笔交易的前提下，进行了第二次买操作；
  • 完成了全部两笔交易。

由于第一个状态的利润显然为 0，因此我们可以不用将其记录。对于剩下的四个状态，我们分别将它们的最大利润记为 buy1，sell1 ，buy2以及 sell2。

这里我们用 buy1′表示第 i−1 天的状态，以便于和第 i 天的状态 buy1进行区分。

对于 buy1而言，在第 i 天我们可以不进行任何操作，保持不变，也可以在未进行任何操作的前提下以 prices[i] 的价格买入股票，那么 buy1的状态转移方程即为：

buy1=max{buy1‘ ,−prices[i]}

对于 sell1而言，在第 i 天我们可以不进行任何操作，保持不变，也可以在只进行过一次买操作的前提下以
prices[i] 的价格卖出股票，那么 sell1的状态转移方程即为：

sell1=max{sell1’ ,buy1‘ +prices[i]}

同理我们可以得到 buy2和 sell2对应的状态转移方程：

buy2=max{buy2′,sell1′−prices[i]}
sell2=max{sell 2‘,buy2′+prices[i]}

无论题目中是否允许「在同一天买入并且卖出」这一操作，最终的答案都不会受到影响，这是因为这一操作带来的收益为零。例如在计算 sell1时，我们直接使用 buy1而不是 buy1′进行转移。buy1比buy1′多考虑的是在第 i 天买入股票的情况，而转移到 sell1 时，考虑的是在第 i 天卖出股票的情况，这样在同一天买入并且卖出收益为零，不会对答案产生影响。

因此，状态转移方程直接可写为

buy1=max{buy1,−prices[i]}

sell1=max{sell1,buy1 +prices[i]}

buy2=max{buy2,sell1−prices[i]}
sell2=max{sell2,buy2+prices[i]}

提示

对于边界条件，我们考虑第 i=0 天时的四个状态：
buy 1 即为以 prices[0] 的价格买入股票，因此 buy1=−prices[0]；

sell1即为在同一天买入并且卖出，因此 sell1=0；

buy2即为在同一天买入并且卖出后再以 prices[0] 的价格买入股票，因此 buy2 =−prices[0]；

同理可得 sell2=0。

我们将这四个状态作为边界条件，从 i=1 开始进行动态规划，即可得到答案。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int buy1 = -prices[0], sell1 = 0;
        int buy2 = -prices[0], sell2 = 0;
        for (int i = 1; i < n; ++i) {
            buy1 = Math.max(buy1, -prices[i]);
            sell1 = Math.max(sell1, buy1 + prices[i]);
            buy2 = Math.max(buy2, sell1 - prices[i]);
            sell2 = Math.max(sell2, buy2 + prices[i]);
        }
        return sell2;
    }
}

复杂度分析：

  • 时间复杂度 O(n) ： 其中 n 是数组 prices 的长度。
  • 空间复杂度 O(1) ： 只使用了常数个变量。

其他解答

解题思路

借鉴买卖股票的最佳时间I的思路，计算 0 到 i 天交易一次的最大收益与 i 到 length 天交易一次的最大收益和。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int maxProfit(int[] prices) {
        int max = 0;
        for (int i = 0; i < prices.length; i++) {
            max = Math.max(max, func(prices, 0, i) + func(prices, i, prices.length));
        }
        return max;
    }

    private int func(int[] prices, int start, int end) {
        int min = prices[start];
        int profit = 0;
        for (int i = start; i < end; i++) {
            profit = Math.max(prices[i] - min, profit);
            min = Math.min(min, prices[i]);
        }
        return profit;
    }
}

买卖股票的最佳时机 IV

题目信息

  • 题目描述：

    给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。

    设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。

示例1:

1
2
3
输入：k = 2, prices = [2,4,1]
输出：2
解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。

示例2:

1
2
3
4
输入：k = 2, prices = [3,2,6,5,0,3]
输出：7
解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
     随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 =

注意

1
1. 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

解题思路

本题难点

股票交易的笔数不确定

具体思路

与其余的股票问题类似，我们使用一系列变量存储「买入」的状态，再用一系列变量存储「卖出」的状态，通过动态规划的方法即可解决本题。

我们用 buy[i] [j] 表示对于数组 prices[0…i] 中的价格而言，进行恰好 j 笔交易，并且当前手上持有一支股票，这种情况下的最大利润；用 sell[i] [j] 表示恰好进行 j 笔交易，并且当前手上不持有股票，这种情况下的最大利润。

那么我们可以对状态转移方程进行推导。对于 buy[i] [j]，我们考虑当前手上持有的股票是否是在第 i 天买入的。如果是第 i 天买入的，那么在第 i−1 天时，我们手上不持有股票，对应状态 sell[i−1] [j]，并且需要扣除 prices[i] 的买入花费；如果不是第 i 天买入的，那么在第 i−1 天时，我们手上持有股票，对应状态 buy[i] [j]。那么我们可以得到状态转移方程：

buy[i] [j]=max{buy[i−1] [j],sell[i−1] [j]−price[i]}

同理对于 sell[i] [j]，如果是第 i 天卖出的，那么在第 i−1 天时，我们手上持有股票，对应状态 buy[i−1] [j−1]，并且需要增加 prices[i] 的卖出收益；如果不是第 i 天卖出的，那么在第 i−1 天时，我们手上不持有股票，对应状态 sell[i−1] [j]。那么我们可以得到状态转移方程：

sell[i] [j]=max{sell[i−1] [j],buy[i−1] [j−1]+price[i]}

由于在所有的 n 天结束后，手上不持有股票对应的最大利润一定是严格由于手上持有股票对应的最大利润的，然而完成的交易数并不是越多越好（例如数组 prices 单调递减，我们不进行任何交易才是最优的），因此最终的答案即为 sell[n−1] [0…k] 中的最大值。

提示

对于 buy[0] [0…k]，由于只有 prices[0] 唯一的股价，因此我们不可能进行过任何交易，那么我们可以将所有的 buy[0] [1…k] 设置为一个非常小的值，表示不合法的状态。而对于 buy[0] [0]，它的值为 −prices[0]，即「我们在第 0 天以 prices[0] 的价格买入股票」是唯一满足手上持有股票的方法。

在设置完边界之后，我们就可以使用二重循环，在 i∈[1,n),j∈[0,k] 的范围内进行状态转移。需要注意的是，sell[i] [j] 的状态转移方程中包含 buy[i−1] [j−1]，在 j=0 时其表示不合法的状态，因此在 j=0 时，我们无需对 sell[i] [j] 进行转移，让其保持值为 0 即可。

本题中 k 的最大值可以达到 10 ^9 ，然而这是毫无意义的，因为 n 天最多只能进行 ⌊n/2⌋ 笔交易，其中 ⌊x⌋ 表示对 x 向下取整。因此我们可以将 k 对 ⌊n/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
class Solution {
    public int maxProfit(int k, int[] prices) {
        if (prices.length == 0) {
            return 0;
        }

        int n = prices.length;
        k = Math.min(k, n / 2);
        int[] buy = new int[k + 1];
        int[] sell = new int[k + 1];

        buy[0] = -prices[0];
        sell[0] = 0;
        for (int i = 1; i <= k; ++i) {
            buy[i] = sell[i] = Integer.MIN_VALUE / 2;
        }

        for (int i = 1; i < n; ++i) {
            buy[0] = Math.max(buy[0], sell[0] - prices[i]);
            for (int j = 1; j <= k; ++j) {
                buy[j] = Math.max(buy[j], sell[j] - prices[i]);
                sell[j] = Math.max(sell[j], buy[j - 1] + prices[i]);   
            }
        }
        return Arrays.stream(sell).max().getAsInt();
    }
}

复杂度分析：

  • 时间复杂度 O(nmin(n,k)) ： 其中 n是数组 prices 的大小，即我们使用二重循环进行动态规划需要的时间。
  • 空间复杂度 O(min(n,k)) ： 一维数组进行动态规划。

其他优秀解答

解题思路

常规的动态规划

  1. 这里的k居然给这么大，其实超出了天数的一半就没有用，因为不会产生这么多交易；
  2. 首先是状态表示，利用一个三维数组，数组值表示当前还有多少钱，三个维度分别代表：第几天，手上是否有股票0没有1有，还剩下多少次买卖的机会；
  3. 然后是状态转移，分为当前持有股票和不持有股票两种状态来转移分析。
  4. 这里以卖出股票来作为完成一次交易的触发条件。

代码

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
class Solution {
    public int maxProfit(int k, int[] prices) {
        int n = prices.length;
        if(n == 0) return 0;

        // 如果k超过了最大可买卖次数，那就将k置为最大买卖次数
        // 最大买卖次数就是天数的一半，如果当前卖出又买入，是没有意义的
        k = Math.min(k, n / 2);

        // 状态表示数组，三个维度分别代表：第几天，手上是否有股票0没有1有，还剩下多少次买卖机会
        // 数组值表示当前还有多少钱
        int[][][] f = new int[n][2][k + 1];
        
        // 设置初始值，第一天手上有股票的状态，就是买入第一天价格的值
        for(int i = 0; i <= k; i++) {
            f[0][1][i] = -prices[0];
        }
        // 状态转移，遍历天数
        for(int i = 1; i < n; i++) {
            // 枚举当天所有可能买卖次数的状态
            for(int j = 0; j <= k; j++) {
                // 当前不持有股票的状态转移
                if(j < k) {
                    // 当前不持有股票，要么前一天也没有股票，要么前一天有股票但是今天卖出了
                    // 如果今天卖出的话，买卖次数就会比前一天少一次，当天是j，那么前一天就是j+1
                    f[i][0][j] = Math.max(f[i - 1][0][j], f[i - 1][1][j + 1] + prices[i]);
                } else {
                    // 剩余买卖次数j等于初始值剩余交易次数k的时候，
                    // 那么说明从来没有产生过交易，所以需要从前一天的不持有状态转移过来
                    f[i][0][j] = f[i - 1][0][j];
                }

                // 当前持有股票的状态转移，要么前一天也有股票，要么前一天不持有股票但是当天买入了股票
                f[i][1][j] = Math.max(f[i - 1][1][j], f[i - 1][0][j] - prices[i]);
            }
        }

        int res = 0;
        // 获取最大值，最大值肯定出现在当前手上不持有股票的状态
        for(int i = 0; i <= k; i ++) {
            res = Math.max(res, f[n - 1][0][i]);
        }
        return res;
    }
}

买卖股票的最佳时机含手续费

题目信息

  • 题目描述：

    给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；非负整数 fee 代表了交易股票的手续费用。

    你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。

    返回获得利润的最大值。

示例1:

1
2
3
4
5
6
7
8
输入: prices = [1, 3, 2, 8, 4, 9], fee = 2
输出: 8
解释: 能够达到的最大利润:  
在此处买入 prices[0] = 1
在此处卖出 prices[3] = 8
在此处买入 prices[4] = 4
在此处卖出 prices[5] = 9
总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8.

注意

1
1. 这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。

解题思路

本题难点

多加了手续费，交易需要扣除手续费，交易的次数越多手续费越多

具体思路

思路类似买卖股票的最佳时机II

  1. 定义状态
    dp[i] [0]表示第 i 天交易完后手里没有股票的最大利润，dp[i] [1] 表示第 i 天交易完后手里持有一支股票的最大利润（i 从 0 开始）。

  2. 考虑 dp[i] [0] 的转移方程，如果这一天交易完后手里没有股票，那么可能的转移状态为前一天已经没有股票，即 dp[i−1] [0]，或者前一天结束的时候手里持有一支股票，即 dp[i−1] [1]，这时候我们要将其卖出，并获得 prices[i] 的收益,但需要支付 fee 的手续费。因此为了收益最大化，我们列出如下的转移方程：

    dp[i] [0]=max{dp[i−1] [0],dp[i−1] [1]+prices[i]-fee}

  3. 再来考虑 dp[i] [1]，按照同样的方式考虑转移状态，那么可能的转移状态为前一天已经持有一支股票，即
    dp[i−1] [1]，或者前一天结束时还没有股票，即 dp[i−1] [0]，这时候我们要将其买入，并减少
    prices[i] 的收益。可以列出如下的转移方程：

    dp[i] [1]=max{dp[i−1] [1],dp[i−1] [0]−prices[i]}

提示

对于初始状态，根据状态定义我们可以知道第 0 天交易结束的时候 dp[0] [0]=0，dp[0] [1]=−prices[0]。

因此，我们只要从前往后依次计算状态即可。由于全部交易结束后，持有股票的收益一定低于不持有股票的收益，因此这时候 dp[n−1] [0] 的收益必然是大于 dp[n−1] [1] 的，最后的答案即为 dp[n−1] [0]。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int maxProfit(int[] prices, int fee) {
        int n = prices.length;
        int[][] dp = new int[n][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for (int i = 1; i < n; ++i) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        }
        return dp[n - 1][0];
    }
}

注意到上面的状态转移方程中，每一天的状态只与前一天的状态有关，而与更早的状态都无关，因此我们不必存储这些无关的状态，只需要将 dp[i−1] [0] 和 dp[i−1] [1] 存放在两个变量中，通过它们计算出 dp[i] [0] 和 dp[i] [1] 并存回对应的变量，以便于第 i+1 天的状态转移即可。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int maxProfit(int[] prices, int fee) {
        int n = prices.length;
        int sell = 0, buy = -prices[0];
        for (int i = 1; i < n; ++i) {
            sell = Math.max(sell, buy + prices[i] - fee);
            buy = Math.max(buy, sell - prices[i]);
        }
        return sell;
    }
}

复杂度分析：

  • 时间复杂度 O(n) ： 其中 n 为数组的长度。一共有 2n 个状态，每次状态转移的时间复杂度为O(1)，因此时间复杂度为 O(2n)=O(n)
  • 空间复杂度 O(1) ： 我们需要开辟 O(n)空间存储动态规划中的所有状态。如果使用空间优化，空间复杂度可以优化至 O(1)。

其他优秀解答

解题思路

贪心算法，换一个角度考虑，将手续费放在买入时进行计算，那么就可以得到一种基于贪心的方法。

我们用 buy 表示在最大化收益的前提下，如果我们手上拥有一支股票，那么它的最低买入价格是多少。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int maxProfit(int[] prices, int fee) {
        int n = prices.length;
        int buy = prices[0] + fee;
        int profit = 0;
        for (int i = 1; i < n; ++i) {
            if (prices[i] + fee < buy) {
                buy = prices[i] + fee;
            } else if (prices[i] > buy) {
                profit += prices[i] - buy;
                buy = prices[i];
            }
        }
        return profit;
    }
}

最佳买卖股票时机含冷冻期

题目信息

  • 题目描述：

    给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。

    设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

示例1:

1
2
3
输入: [1,2,3,0,2]
输出: 3 
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

注意

1
2
1. 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
2. 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

解题思路

本题难点

卖出后有冷冻期，不可以频繁的交易，要看准时机，才能获益最大

具体思路

一种常用的方法是将「买入」和「卖出」分开进行考虑：「买入」为负收益，而「卖出」为正收益。在初入股市时，你只有「买入」的权利，只能获得负收益。而当你「买入」之后，你就有了「卖出」的权利，可以获得正收益。显然，我们需要尽可能地降低负收益而提高正收益，因此我们的目标总是将收益值最大化。因此，我们可以使用动态规划的方法，维护在股市中每一天结束后可以获得的「累计最大收益」，并以此进行状态转移，得到最终的答案。

我们用 f[i] 表示第 i 天结束之后的「累计最大收益」。根据题目描述，由于我们最多只能同时买入（持有）一支股票，并且卖出股票后有冷冻期的限制，因此我们会有三种不同的状态：

  • 我们目前持有一支股票，对应的「累计最大收益」记为 f[i] [0]；
  • 我们目前不持有任何股票，并且处于冷冻期中，对应的「累计最大收益」记为 f[i] [1]；
  • 我们目前不持有任何股票，并且不处于冷冻期中，对应的「累计最大收益」记为 f[i] [2]。

这里的「处于冷冻期」指的是在第 ii 天结束之后的状态。也就是说：如果第 ii 天结束之后处于冷冻期，那么第 i+1 天无法买入股票。

在第 i 天时，我们可以在不违反规则的前提下进行「买入」或者「卖出」操作，此时第 i 天的状态会从第 i−1 天的状态转移而来；我们也可以不进行任何操作，此时第 i 天的状态就等同于第 i−1 天的状态。那么我们分别对这三种状态进行分析：

  • 对于 f[i] [0]，我们目前持有的这一支股票可以是在第 i−1 天就已经持有的，对应的状态为 f[i−1] [0]；或者是第 i 天买入的，那么第 i−1 天就不能持有股票并且不处于冷冻期中，对应的状态为 f[i−1] [2] 加上买入股票的负收益 prices[i]。因此状态转移方程为：

    f[i] [0]=max(f[i−1] [0],f[i−1] [2]−prices[i])

  • 对于 f[i] [1]，我们在第 i 天结束之后处于冷冻期的原因是在当天卖出了股票，那么说明在第 i−1 天时我们必须持有一支股票，对应的状态为 f[i−1] [0] 加上卖出股票的正收益 prices[i]。因此状态转移方程为：

    f[i] [1]=f[i−1] [0]+prices[i]

  • 对于 f[i] [2]，我们在第 i 天结束之后不持有任何股票并且不处于冷冻期，说明当天没有进行任何操作，即第 i−1 天时不持有任何股票：如果处于冷冻期，对应的状态为 f[i−1] [1]；如果不处于冷冻期，对应的状态为 f[i−1] [2]。因此状态转移方程为：

    f[i] [2]=max(f[i−1] [1],f[i−1] [2])

这样我们就得到了所有的状态转移方程。如果一共有 nn 天，那么最终的答案即为：

max(f[n−1] [0],f[n−1] [1],f[n−1] [2])

注意到如果在最后一天（第 n−1 天）结束之后，手上仍然持有股票，那么显然是没有任何意义的。因此更加精确地，最终的答案实际上是 f[n−1] [1] 和 f[n−1] [2] 中的较大值，即：

max(f[n−1] [1],f[n−1] [2])

提示

在第 0 天时，如果持有股票，那么只能是在第 0 天买入的，对应负收益 −prices[0]；如果不持有股票，那么收益为零。注意到第 0 天实际上是不存在处于冷冻期的情况的，但我们仍然可以将对应的状态 f[0] [1] 置为零。

这样我们就可以从第 1 天开始，根据上面的状态转移方程进行进行动态规划，直到计算出第 n−1 天的结果。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length == 0) {
            return 0;
        }

        int n = prices.length;
        // f[i][0]: 手上持有股票的最大收益
        // f[i][1]: 手上不持有股票，并且处于冷冻期中的累计最大收益
        // f[i][2]: 手上不持有股票，并且不在冷冻期中的累计最大收益
        int[][] f = new int[n][3];
        f[0][0] = -prices[0];
        for (int i = 1; i < n; ++i) {
            f[i][0] = Math.max(f[i - 1][0], f[i - 1][2] - prices[i]);
            f[i][1] = f[i - 1][0] + prices[i];
            f[i][2] = Math.max(f[i - 1][1], f[i - 1][2]);
        }
        return Math.max(f[n - 1][1], f[n - 1][2]);
    }
}

注意到上面的状态转移方程中，
f[i] […] 只与 f[i−1] […] 有关，而与 f[i−2] […] 及之前的所有状态都无关，因此我们不必存储这些无关的状态。也就是说，我们只需要将 f[i−1] [0]，f[i−1] [1]，f[i−1] [2] 存放在三个变量中，通过它们计算出 f[i] [0]，f[i] [1]，f[i] [2] 并存回对应的变量，以便于第 i+1 天的状态转移即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length == 0) {
            return 0;
        }

        int n = prices.length;
        int f0 = -prices[0];
        int f1 = 0;
        int f2 = 0;
        for (int i = 1; i < n; ++i) {
            int newf0 = Math.max(f0, f2 - prices[i]);
            int newf1 = f0 + prices[i];
            int newf2 = Math.max(f1, f2);
            f0 = newf0;
            f1 = newf1;
            f2 = newf2;
        }

        return Math.max(f1, f2);
    }
}

复杂度分析：

  • 时间复杂度 O(n) ： 其中 n 为数组 prices 的长度。
  • 空间复杂度 O(1) ： 我们需要 3n 的空间存储动态规划中的所有状态，对应的空间复杂度为 O(n)。如果使用空间优化，空间复杂度可以优化至 O(1)。