MarsCode算法题之股票市场交易策略优化

这道题比较难的地方就在于状态比较多，我们需要耐心的分析出各个状态的情况和如何初始化，分析完之后，这道题其实也就解决了大半了。我们一共有四种状态，持有股票、不持有股票、当天卖出和冷冻期，状态较多，我们可以从容易的开始，一步一步逐个击破。

2301_79318558

887人浏览 · 2024-11-07 20:00:00

2301_79318558 · 2024-11-07 20:00:00 发布

1.问题描述

小R近期表现出色，公司决定以股票的形式给予奖励，并允许他在市场上进行交易以最大化收益。给定一个数组，数组中的第 i 个元素代表第 i 天的股票价格。小R需要设计一个算法来实现最大利润。

股票交易规则如下：

小R可以多次买卖股票，但在买入新的股票前必须卖出之前的股票。
每次卖出股票后存在一天的冷冻期，在冷冻期内小R不能购买股票。

你的任务是帮助小R计算出在遵守交易规则的情况下能够获得的最大利润。

stocks: 一个整数列表，表示连续几天内的股票价格。

示例1

输入：stocks = [1, 2]
输出：1

示例2

输入：stocks = [2, 1]
输出：0

示例3

输入：stocks = [1, 2, 3, 0, 2]
输出：3

示例4

输入：stocks = [2, 3, 4, 5, 6, 7]
输出：5

示例5

输入：stocks = [1, 6, 2, 7, 13, 2, 8]
输出：12

难度等级

中等

题目链接

股票市场交易策略优化

2.解题思路

这道股市市场交易的题目我们得用动态规划的思想来解决，有点困难，因为加入冷冻期之后，股票的状态有点多，不过没关系，我们一步一步来分析。

在这道题里面，一共有四种状态，第一种是持有股票的状态，第二种是不持有股票的状态，第三种当天卖出股票的状态，第四种是冷冻期的状态。

首先第一步，我们得有一个dp数组。创建一个dp[stocks.length][4]的数组，dp数组的含义是第i天第k种状态的收益。在这道题里我们一共有4种状态，0 表示持有股票的状态、1 表示不持有股票的状态、2 表示当天卖出股票的状态、3 表示冷冻期的状态。如果一开始不知道有多少种状态，可以向空着，一步一步分析完再来填写。

         //创建dp数组:第i天第j中状态的收益
         int[][] dp = new int[stocks.length][4];

明确了dp数组的含义之后，我们接下来就要确定递推公式。我们先从简单的开始入手。

如果当天是冷冻期的状态，那么前一天一定是卖出了股票，所以我们就可以得到冷冻期状态的递推公式：dp[i][3] = dp[i-1][2]。

             //状态四:今天是冷冻期的状态
             dp[i][3] = dp[i-1][2];

如果当天是卖出股票的状态，那么前一天一定持有股票，卖出股票就能够得到收益，所以我们也可以得到当天卖出股票状态的递推公式：dp[i][2] = dp[i-1][0] + stocks[i]。

             //状态三:今天卖出股票的状态
             dp[i][2] = dp[i-1][0] + stocks[i];

如果当天是不持有股票的状态，那么可能是前一天我们卖出了股票(dp[i-1][2])，也可能是前一天是冷冻期(dp[i-1][3])，还有可能前一天我们本来就不持有股票(dp[i-1][1])，所以我们也可以得到不持有股票状态的递推公式:dp[i][1] = max(dp[i-1][2],dp[i-1][3],dp[i-1][1])。

             //状态二:不持有股票的状态
             dp[i][1] = Math.max(Math.max(dp[i-1][1],dp[i-1][3]),dp[i-1][2]);

如果当天是持有股票的状态，那么可能是我们前一天就持有股票(dp[i-1][0])，也可能是我们前一天是冷冻期，过了冷冻期今天买股票，买股票是要扣钱的(dp[i-1][3] - stocks[i])，还有一种可能是我们前一天不是冷冻期但是也没有持有股票，然后今天买股票(dp[i-1][1] - stocks[i])。

             //状态一:持有股票的状态
             dp[i][0] = Math.max(Math.max(dp[i-1][0],dp[i-1][3] - stocks[i]),dp[i-1][1] - stocks[i]);

这样一通分析，我们的递推公式就全部出来了，接着我们就要来初始化一下我们的dp数组。根据dp数组的含义和我们四个状态的递推公式，来初始化。还是从简单的开始来。冷冻期状态，我们没有-1天，所以第0天不可能是冷冻期，初始化为0。卖出股票状态，我们第0天还没开始操作了，所以也初始化为0。不持有股票的状态，我们第0天肯定是持有股票的，这是不然都没办法交易，所以也初始化为0。持有股票的状态，我们第0天肯定要持有股票，才有后续的操作，所以第0天我们要买入股票，初始化为-stocks[0]。这样一来，我们的初始化就全部完成了。

         //初始化dp数组
         dp[0][0] = -stocks[0];
         dp[0][1] = 0;
         dp[0][2] = 0;
         dp[0][3] = 0;

可能有人会问，股票不是公司奖励的吗？为什么初始化的时候要扣掉，这里我其实也不知道怎么解释，只能强行解释为公司给他股票也是要通过交易的，而本金就是他之前表现所值的钱，要减去本金，剩下的才是利润收益。我一开始也是初始化为0，但是发现过不了，然后摸着石头过河瞎初始化，初始化为-stocks[0]的时候，突然就过了。

接着只要遍历数组，递推公式进行推到即可。最大的收益可能在不持有股票，今天卖出股票和冷冻期中的其中一个，我们去最后一天这三个的最大值就可以了。为什么没有状态一持有股票呢？因为卖掉肯定赚钱，买还要倒扣钱。

         return Math.max(dp[stocks.length - 1][3], Math.max(dp[stocks.length - 1][1], dp[stocks.length - 1][2]));

3.代码展示

public class Main {
    public static int solution(int[] stocks) {
        // Please write your code here
         //创建dp数组:第i天第j中状态的收益
         int[][] dp = new int[stocks.length][4];
         //初始化dp数组
         dp[0][0] = -stocks[0];
         dp[0][1] = 0;
         dp[0][2] = 0;
         for(int i = 1;i< stocks.length;i++){
             //状态一:持有股票的状态
             dp[i][0] = Math.max(Math.max(dp[i-1][0],dp[i-1][3] - stocks[i]),dp[i-1][1] - stocks[i]);
             //状态二:不持有股票的状态
             dp[i][1] = Math.max(Math.max(dp[i-1][1],dp[i-1][3]),dp[i-1][2]);
             //状态三:今天卖出股票的状态
             dp[i][2] = dp[i-1][0] + stocks[i];
             //状态四:今天是冷冻期的状态
             dp[i][3] = dp[i-1][2];
         }
         return Math.max(dp[stocks.length - 1][3], Math.max(dp[stocks.length - 1][1], dp[stocks.length - 1][2]));
    }

    public static void main(String[] args) {
        // You can add more test cases here
        System.out.println(solution(new int[]{1, 2}) == 1);
        System.out.println(solution(new int[]{2, 1}) == 0);
        System.out.println(solution(new int[]{1, 2, 3, 0, 2}) == 3);
        System.out.println(solution(new int[]{2, 3, 4, 5, 6, 7}) == 5);
        System.out.println(solution(new int[]{1, 6, 2, 7, 13, 2, 8}) == 12);
    }
}