[−][src]Function leetcode_for_rust::cd0188_best_time_to_buy_and_sell_stock_iv::max_profit
pub fn max_profit(k: i32, prices: Vec<i32>) -> i32
Solutions
Approach 1: Dynamic Programming
-
Time complexity: O(n*k)
-
Space complexity: O(n)
-
Runtime: 240 ms
-
Memory: 223.8 MB
use std::cmp; impl Solution { pub fn max_profit(k: i32, prices: Vec<i32>) -> i32 { if prices.len() < 2 { return 0; } let k = cmp::min(k as usize, prices.len() / 2 + 1); let mut profits = vec![vec![0; prices.len()]; (k+1)]; let mut max_profit = 0; for kk in 1..=k { let mut tmp_max = profits[kk-1][0] - prices[0]; for i in 1..prices.len() { profits[kk][i] = cmp::max(profits[kk][i-1], prices[i] + tmp_max); tmp_max = cmp::max(tmp_max, profits[kk-1][i] - prices[i]); max_profit = cmp::max(profits[kk][i], max_profit); } } max_profit } }
Approach 2: Dynamic Programming
-
Time complexity: O(n*k)
-
Space complexity: O(n)
-
Runtime: 0 ms
-
Memory: 2.9 MB
use std::cmp::max; impl Solution { pub fn max_profit(k: i32, prices: Vec<i32>) -> i32 { if prices.len() < 2 { return 0; } let k = k as usize; let mut max_profit = 0; if k >= prices.len() / 2 { for i in 1..prices.len() { max_profit += max(0, prices[i] - prices[i - 1]); } return max_profit; } let mut profits = vec![vec![0; prices.len()]; k+1]; for kk in 1..=k { let mut tmp_max = profits[kk-1][0] - prices[0]; for i in 1..prices.len() { profits[kk][i] = max(profits[kk][i-1], prices[i] + tmp_max); tmp_max = max(tmp_max, profits[kk-1][i] - prices[i]); max_profit = max(profits[kk][i], max_profit); } } max_profit } }