[−][src]Function leetcode_for_rust::cd0123_best_time_to_buy_and_sell_stock_iii::max_profit

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

Solutions

Approach 1: Dynamic Programming

Time complexity: O(n)
Space complexity: O(n)
Runtime: 16 ms
Memory: 5.7 MB

use std::cmp;

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

        let mut result = 0;
        let n = prices.len();
        let mut profits = vec![vec![vec![0; 2]; 3]; n];
        profits[0][0][1] = -prices[0];
        profits[0][1][1] = -prices[0];

        for i in 1..n {
            profits[i][0][0] = profits[i - 1][0][0];
            profits[i][0][1] = cmp::max(profits[i - 1][0][1], profits[i - 1][0][0] - prices[i]);

            profits[i][1][0] = cmp::max(profits[i - 1][1][0], profits[i - 1][0][1] + prices[i]);
            profits[i][1][1] = cmp::max(profits[i - 1][1][1], profits[i - 1][1][0] - prices[i]);

            profits[i][2][0] = cmp::max(profits[i - 1][2][0], profits[i - 1][1][1] + prices[i]);
        }

        result = cmp::max(profits[n-1][0][0], cmp::max(profits[n-1][1][0], profits[n-1][2][0]));
        result
    }
}

Approach 2: Dynamic Programming

Time complexity: O(n)
Space complexity: O(1)
Runtime: 0 ms
Memory: 2.6 MB

use std::cmp::max;

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

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

        max_profit
    }
}

reference: