[−][src]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 } }