struct Solution {}
use std::cmp::max;
impl Solution {
    //按照框架来写的方法
    pub fn max_profit(prices: Vec<i32>) -> i32 {
        if prices.len() <= 0 {
            return 0;
        }
        let mut dp = vec![vec![0; 2]; prices.len()];
        dp[0][0] = 0;
        dp[0][1] = -prices[0]; //初始不持有股票的利润是0,持有股票表示第一天买入了,那么他的利润就是负数
        for i in 1..prices.len() {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]); //第i天不持有股票不外乎两种情况,前一天没有持有股票,卖掉了前一天持有的股票
            let mut last = 0;
            if i >= 2 {
                last = dp[i - 2][0];
            }
            dp[i][1] = max(dp[i - 1][1], last - prices[i]); //当前持有股票,不外乎前一天持有股票,或者今天买入了,今天买入参考利润应该是前前天的
        }
        dp[prices.len() - 1][0]
    }
}

#[cfg(test)]
mod test {
    use super::*;

    #[test]
    fn test() {
        assert_eq!(Solution::max_profit(vec![1, 2, 3, 0, 2]), 3);
    }
}