struct Solution {}
use std::cmp::max;
impl Solution {
    //没必要动态分配那么多,因为至于上一个状态有关
    pub fn max_profit(k: i32, prices: Vec<i32>) -> i32 {
        if k == 0 || prices.len() == 0 {
            return 0;
        }
        let mut k = k as usize;
        if k >= prices.len() / 2 + 1 {
            k = prices.len() / 2 + 1; //最多进行prices.len()/2次交易,不可能进行更多了,一买一卖
        }
        let mut dp = vec![vec![0; 2]; k as usize];

        println!("k={},priceslen={}", k, prices.len());

        for i in 0..k {
            dp[i][1] = -prices[0]; //剩下k-1次交易,持有股票 ,
        }
        //        println!("dp0={:?}", dp[0]);
        for i in 1..prices.len() {
            let price = prices[i];
            for j in 0..k as usize {
                //剩下j次交易,不持有股票,
                dp[j][0] = max(dp[j][0], dp[j][1] + price);
                let mut last = 0;
                if j < k - 1 {
                    last = dp[j + 1][0];
                }
                //剩下j次交易,持有股票
                dp[j][1] = max(dp[j][1], last - price);
            }
            println!("i={}", i);
            //            println!("dp[{}]={:?}", i, dp[i]);
        }
        dp[0][0]
    }
}
#[cfg(test)]
mod test {
    use super::*;

    #[test]
    fn test() {
        // [3,2,6,5,0,3], k = 2
        assert_eq!(Solution::max_profit(2, vec![3, 2, 6, 5, 0, 3, 2, 3]), 7);
        
    }
}