当前位置：首页 > article >正文

【动态规划】股票市场交易策略优化

article 2024/11/30 17:23:55

文章目录

- - 一、问题描述
  - 二、解决思路
  - - 状态转移
    - 初始化
    - 最终结果
  - 三、代码实现
  - 执行流程解析
  - 时间和空间复杂度

一、问题描述

我们要解决的是一个关于股票买卖的问题：给定一个股票价格数组 stocks，每一天的价格为数组中的一个元素。我们可以通过买入和卖出的操作来获取收益，但需要遵守以下规则：

每次买入前，必须先卖出之前的股票（即不能同时持有两次未卖出的股票）。
卖出股票后有一个冷冻期，也就是说，在卖出后的第二天才能继续买入股票。

我们的目标是：计算出在满足上述规则的情况下，最大可以获得的利润。

例如，给定数组 [1, 2, 3, 0, 2]：

第一天买入，花费 -1；
第二天卖出，收入 +2；
第四天再次买入，花费 -0；
第五天卖出，收入 +2。总收益为 3。

二、解决思路

这是一个经典的 动态规划 问题。我们通过记录每一天的三种可能状态来逐步计算：

持有股票（hold）：表示当天我们手中有股票的情况下，最大可能的收益。
未持有股票但不在冷冻期（unhold）：表示当天我们手中没有股票，并且可以自由操作的情况下，最大可能的收益。
未持有股票且处于冷冻期（cooldown）：表示当天我们手中没有股票，但因为刚卖出，处于冷冻期的情况下，最大可能的收益。

状态转移

持有股票（hold）：
- 要么昨天已经持有股票，今天保持不动（收益不变）。
- 要么昨天没有股票（并且不在冷冻期），今天买入股票（收益减去今天的价格）。
- 状态转移公式：
未持有股票但不在冷冻期（unhold）：
- 要么昨天已经没有股票且不在冷冻期，今天也不操作（收益不变）。
- 要么昨天刚结束冷冻期，今天自由操作（收益等于昨天冷冻期的收益）。
- 状态转移公式：
未持有股票且处于冷冻期（cooldown）：
- 必须是昨天持有股票，今天卖出进入冷冻期（收益增加今天的价格）。
- 状态转移公式：

初始化

第一天持有股票：hold[0] = -stocks[0]（买入股票后收益为负）。
第一天未持有股票且不在冷冻期：unhold[0] = 0（什么都不做，收益为 0）。
第一天未持有股票且处于冷冻期：cooldown[0] = 0（第一天不可能处于冷冻期）。

最终结果

最后一天的最大利润一定是：在这里插入图片描述

因为只有未持有股票时，收益才可能是最大值。

三、代码实现

public class Main {
    public static int solution(int[] stocks) {
        if (stocks == null || stocks.length == 0) {
            return 0; // 没有数据时，最大收益为 0
        }

        // 初始化第 1 天的三种状态
        int hold = -stocks[0];      // 第一天买入股票，收益为负的价格
        int unhold = 0;            // 第一天不持有股票，收益为 0
        int cooldown = 0;          // 第一天冷冻期不可能发生，收益为 0

        // 从第 2 天开始计算
        for (int i = 1; i < stocks.length; i++) {
            // 暂存之前的状态值，用于计算
            int prevHold = hold;
            int prevUnhold = unhold;
            int prevCooldown = cooldown;

            // 更新持有股票状态
            hold = Math.max(prevHold, prevUnhold - stocks[i]);
            // 更新未持有股票且不在冷冻期状态
            unhold = Math.max(prevUnhold, prevCooldown);
            // 更新未持有股票且处于冷冻期状态
            cooldown = prevHold + stocks[i];
        }

        // 最终结果是未持有股票的两种状态的最大值
        return Math.max(unhold, cooldown);
    }

    public static void main(String[] args) {
        // 测试用例
        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
    }
}