Function leetcode_for_rust::cd0188_best_time_to_buy_and_sell_stock_iv::max_profit

pub fn max_profit(k: i32, prices: Vec<i32>) -> i32

Solutions

Approach 1: Dynamic Programming

• Time complexity: O(n*k)

• Space complexity: O(n)

• Runtime: 240 ms

• Memory: 223.8 MB

use std::cmp;

impl Solution {
    pub fn max_profit(k: i32, prices: Vec<i32>) -> i32 {
        if prices.len() < 2 { return 0; }

        let k = cmp::min(k as usize, prices.len() / 2 + 1);
        let mut profits = vec![vec![0; prices.len()]; (k+1)];
        let mut max_profit = 0;
        for kk in 1..=k {
            let mut tmp_max = profits[kk-1][0] - prices[0];
            for i in 1..prices.len() {
                profits[kk][i] = cmp::max(profits[kk][i-1], prices[i] + tmp_max);
                tmp_max       = cmp::max(tmp_max, profits[kk-1][i] - prices[i]);
                max_profit    = cmp::max(profits[kk][i], max_profit);
            }
        }

        max_profit

    }
}

Approach 2: Dynamic Programming

• Time complexity: O(n*k)

• Space complexity: O(n)

• Runtime: 0 ms

• Memory: 2.9 MB

use std::cmp::max;

impl Solution {
    pub fn max_profit(k: i32, prices: Vec<i32>) -> i32 {
        if prices.len() < 2 { return 0; }

        let k = k as usize;
        let mut max_profit = 0;
        if k >= prices.len() / 2 {
            for i in 1..prices.len() {
                max_profit += max(0, prices[i] - prices[i - 1]);
            }

            return max_profit;
        }

        let mut profits = vec![vec![0; prices.len()]; k+1];
        for kk in 1..=k {
            let mut tmp_max = profits[kk-1][0] - prices[0];
            for i in 1..prices.len() {
                profits[kk][i] = max(profits[kk][i-1], prices[i] + tmp_max);
                tmp_max       = max(tmp_max, profits[kk-1][i] - prices[i]);
                max_profit    = max(profits[kk][i], max_profit);
            }
        }

        max_profit

    }
}