Function leetcode_for_rust::cd0714_best_time_to_buy_and_sell_stock_with_transaction_fee::max_profit

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

Solutions

Approach 1: Dynamic Programming

• Time complexity: O(n)

• Space complexity: O(n)

• Runtime: 8 ms

• Memory: 3.7 MB

use std::cmp::max;

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

        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] - fee);
            tmp_max = max(tmp_max, profits[i - 1] - prices[i]);
            max_profit = max(max_profit, profits[i]);
        }
        max_profit
    }
}

Approach 2: Dynamic Programming

• Time complexity: O(n)

• Space complexity: O(n)

• Runtime: 8 ms

• Memory: 3.6 MB

use std::cmp::max;

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

       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] - fee);
           buy[i] = max(buy[i - 1], sell[i - 1] - prices[i]);
       }
       sell[prices.len() - 1]
   }
}

Approach 3: Dynamic Programming

• Time complexity: O(n)

• Space complexity: O(n)

• Runtime: 12 ms

• Memory: 3.7 MB

use std::cmp::max;

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

        let mut cash = 0;
        let mut hold = -prices[0];
        for i in 1..prices.len() {
            cash = max(cash, hold + prices[i] - fee);
            hold = max(hold, cash - prices[i]);
        }
        cash
    }
}