[−][src]Function leetcode_for_rust::cd0123_best_time_to_buy_and_sell_stock_iii::max_profit
pub fn max_profit(prices: Vec<i32>) -> i32
Solutions
Approach 1: Dynamic Programming
-
Time complexity: O(n)
-
Space complexity: O(n)
-
Runtime: 16 ms
-
Memory: 5.7 MB
use std::cmp; impl Solution { pub fn max_profit(prices: Vec<i32>) -> i32 { if prices.len() < 2 { return 0; } let mut result = 0; let n = prices.len(); let mut profits = vec![vec![vec![0; 2]; 3]; n]; profits[0][0][1] = -prices[0]; profits[0][1][1] = -prices[0]; for i in 1..n { profits[i][0][0] = profits[i - 1][0][0]; profits[i][0][1] = cmp::max(profits[i - 1][0][1], profits[i - 1][0][0] - prices[i]); profits[i][1][0] = cmp::max(profits[i - 1][1][0], profits[i - 1][0][1] + prices[i]); profits[i][1][1] = cmp::max(profits[i - 1][1][1], profits[i - 1][1][0] - prices[i]); profits[i][2][0] = cmp::max(profits[i - 1][2][0], profits[i - 1][1][1] + prices[i]); } result = cmp::max(profits[n-1][0][0], cmp::max(profits[n-1][1][0], profits[n-1][2][0])); result } }
Approach 2: Dynamic Programming
-
Time complexity: O(n)
-
Space complexity: O(1)
-
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 kk = 2; let mut profits = vec![vec![0; prices.len()]; kk+1]; let mut max_profit = 0; for k in 1..=kk { let mut tmp_max = profits[k-1][0] - prices[0]; for i in 1..prices.len() { profits[k][i] = max(profits[k][i-1], prices[i] + tmp_max); tmp_max = max(tmp_max, profits[k-1][i] - prices[i]); max_profit = max(profits[k][i], max_profit); } } max_profit } }
reference: