[−][src]Function leetcode_for_rust::cd0309_best_time_to_buy_and_sell_stock_with_cooldown::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] } }