1
2
3

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

1
2

输入: prices = [1]
输出: 0

  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
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111

// @lc code=start
impl Solution {
    /// ## 解题思路
    /// - 动态规划
    /// 1. 投资者在整个过程中的每天存在3种状态:
    ///    a. 未投资(uninvested): 此时投资者手中没有股票, 且不在冷静期中, 那么当天(day)投资者有两种策略:
    ///       a1. 不买入. 此时投资收益不变, 第二天状态保持为未投资(invested)状态;
    ///       a2. 买入当天股票, 此时收益 -prices[day]. 第二天状态变为已投资状态(invested);
    ///    b. 已投资(invested): 此时投资者手中已经有了一支股票, 那么此时投资者也有两种策略:
    ///       b1. 不卖出. 此时投资收益不变, 收益profile维持不变, 第二天状态继续维持已投资状态(invested);
    ///       b2. 卖出手中股票. 此时投资收益 +prices[day]. 第二天状态将变为冷静期(cooldown);
    ///    c. 冷静期(cooldown): 此时投资者处于冷静期,此时只有一个策略:
    ///       c1. 无法买卖. 此时投资收益维持不变. 第二天状态变为未投资(uninvested)状态;
    pub fn max_profit0(prices: Vec<i32>) -> i32 {
        use std::collections::HashMap;

        #[derive(PartialEq, Eq, Hash, Copy, Clone)]
        enum Invested {
            Yes,
            No,
            Cooldown,
        }
        fn dp(
            prices: &[i32],
            day: usize,
            invested: Invested,
            memo: &mut HashMap<(usize, Invested), i32>,
        ) -> i32 {
            if day == prices.len() {
                0
            } else if let Some(profit) = memo.get(&(day, invested)) {
                *profit
            } else {
                let rez = match invested {
                    Invested::Yes => dp(prices, day + 1, invested, memo)
                        .max(prices[day] + dp(prices, day + 1, Invested::Cooldown, memo)),
                    Invested::No => dp(prices, day + 1, invested, memo)
                        .max(-prices[day] + dp(prices, day + 1, Invested::Yes, memo)),
                    Invested::Cooldown => dp(prices, day + 1, Invested::No, memo),
                };
                memo.insert((day, invested), rez);
                rez
            }
        }

        dp(&prices, 0, Invested::No, &mut HashMap::new())
    }

    /// 优化2:
    pub fn max_profit1(prices: Vec<i32>) -> i32 {
        #[derive(Default, Clone)]
        struct Profit {
            invested: i32,
            uninvested: i32,
            cooldown: i32,
        }
        let n = prices.len();
        let mut profits = vec![Profit::default(); n + 1];
        for day in (0..n).rev() {
            profits[day] = Profit {
                invested: profits[day + 1]
                    .invested
                    .max(prices[day] + profits[day + 1].cooldown),
                uninvested: profits[day + 1]
                    .uninvested
                    .max(-prices[day] + profits[day + 1].invested),
                cooldown: profits[day + 1].uninvested,
            }
        }

        profits[0].uninvested
    }

    /// 优化3: 实用一个变量代替数组
    pub fn max_profit2(prices: Vec<i32>) -> i32 {
        #[derive(Default, Clone)]
        struct Profit {
            invested: i32,
            uninvested: i32,
            cooldown: i32,
        }
        prices
            .into_iter()
            .rev()
            .fold(Profit::default(), |profit, price| Profit {
                invested: profit.invested.max(price + profit.cooldown),
                uninvested: profit.uninvested.max(-price + profit.invested),
                cooldown: profit.uninvested,
            })
            .uninvested
    }

    /// 优化4: 实用元组代替结构体定义
    pub fn max_profit(prices: Vec<i32>) -> i32 {
        prices
            .into_iter()
            .rev()
            .fold((0, 0, 0), |profit, price| {
                (
                    profit.0.max(price + profit.2),
                    profit.1.max(-price + profit.0),
                    profit.1,
                )
            })
            .1
    }
}
// @lc code=end

struct Solution;