Function max_profit

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

Solutions

Approach 1: Dynamic Programming

• Time complexity: O(n)

• Space complexity: O(n)

• 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 cooldown = 1;
        let mut profits = vec![0; prices.len()];
        let mut max_profit = 0;
        let mut tmp_max = profits[0] - prices[0];

        for i in 1..prices.len() {
            profits[i] = max(profits[i - 1], tmp_max + prices[i]);
            tmp_max    = max(tmp_max, if i > cooldown { profits[i - 1 - cooldown] } else { profits[i - 1] } - prices[i]);
            max_profit = max(profits[i], max_profit);
        }
        max_profit
    }
}

Approach 2: Dynamic Programming

• Time complexity: O(n)

• Space complexity: O(n)

• Runtime: 0 ms

• Memory: 2.5 MB

use std::cmp::max;

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

        let cooldown = 1;
        let mut sell = vec![0; prices.len()];
        let mut buy = vec![0; prices.len()];
        buy[0] = -prices[0];

        for i in 1..prices.len() {
            sell[i] = max(sell[i - 1], buy[i - 1] + prices[i]);
            buy[i]  = max(buy[i - 1], if i > cooldown { sell[i - 1 - cooldown] } else { sell[i - 1] } - prices[i]);
        }
        sell[prices.len() - 1]
    }
}