//k 很大的时候
    fn simple_max_profit(prices: &Vec<i32>) -> i32 {
        if prices.len() <= 0 {
            return 0;
        }
        let mut hold = -prices[0]; //持有股票
        let mut cash = 0; // 不持有股票
        for i in 1..prices.len() {
            cash = max(cash, hold + prices[i]); //第i天不持有股票不外乎两种情况,前一天没有持有股票,卖掉了前一天持有的股票
            hold = max(hold, cash - prices[i]); //当前持有股票,不外乎前一天持有股票,或者今天买入了
        }
        cash
    }
    //考虑到1,5,7,30这样的序列,中间是不可能卖出的,可以移除大部分值
    fn remove_inscrease_order(prices: Vec<i32>) -> Vec<i32> {
        if prices.len() <= 0 {
            return prices;
        }
        let mut res = Vec::new();
        let mut cur_min = prices[0];
        let mut cur_max = prices[0];
        res.push(cur_min);
        for i in 1..prices.len() {
            let p = prices[i];
            if p < cur_max {
                //碰到了新一个由低到高
                if cur_max > cur_min {
                    res.push(cur_max);
                }
                res.push(p);
                cur_min = p;
            }
            cur_max = p;
        }
        if cur_max > cur_min {
            res.push(cur_max);
        }
        res
    }
    /*
    终极优化问题
    1. 如果k>prices.len,那么就退化成了不限制次数,
    2. 考虑到1,5,7,30这样的序列,中间是不可能卖出的,可以移除大部分值
    */
    pub fn max_profit(k: i32, prices: Vec<i32>) -> i32 {
        println!("k={},priceslen={}", k, prices.len());
        if k == 0 || prices.len() == 0 {
            return 0;
        }
        let mut k = k as usize;
        if k >= prices.len() {
            return Self::simple_max_profit(&prices);
        }
        let prices = Self::remove_inscrease_order(prices);
        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]
    }