[−][src]Function leetcode_for_rust::cd0121_best_time_to_buy_and_sell_stock::max_profit
pub fn max_profit(prices: Vec<i32>) -> i32
Solutions
Approach 1: Dynamic Programming
-
Time complexity: O(3n)
-
Space complexity: O(n)
-
Runtime: 0 ms
-
Memory: 3.6 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 mut profits = vec![vec![0; 3]; prices.len()]; profits[0][1] = -prices[0]; for i in 1..prices.len() { profits[i][0] = profits[i - 1][0]; profits[i][1] = cmp::max(profits[i - 1][1], profits[i - 1][0] - prices[i]); profits[i][2] = profits[i - 1][1] + prices[i]; result = cmp::max(result, cmp::max(profits[i][0], cmp::max(profits[i][1], profits[i][2]))); } result } }
Approach 2: Dynamic Programming
-
Time complexity: O(n)
-
Space complexity: O(n)
-
Runtime: 0 ms
-
Memory: 2.7 MB
impl Solution { pub fn max_profit(prices: Vec<i32>) -> i32 { if prices.len() < 2 { return 0; } let mut profits = vec![0; prices.len()]; profits[0] = -prices[0]; for i in 1..prices.len() { if profits[i - 1] < 0 { profits[ i - 1] = 0; } profits[i] = profits[i - 1] - prices[i - 1] + prices[i]; } profits.sort(); *profits.last().unwrap() } }
Approach 3: Dynamic Programming
-
Time complexity: O(n)
-
Space complexity: O(n)
-
Runtime: 0 ms
-
Memory: 2.6 MB
use std::cmp; impl Solution { pub fn max_profit(prices: Vec<i32>) -> i32 { if prices.len() < 2 { return 0; } let mut profits = vec![0; prices.len()]; let mut max_profit = 0; let mut tmp_min = prices[0]; for i in 1..prices.len() { profits[i] = cmp::max(profits[i - 1], prices[i] - tmp_min); tmp_min = cmp::min(tmp_min, prices[i]); max_profit = cmp::max(profits[i], max_profit); } max_profit } }
Approach 4: Dynamic Programming
-
Time complexity: O(n)
-
Space complexity: O(n)
-
Runtime: 0 ms
-
Memory: 2.6 MB
use std::cmp; impl Solution { pub fn max_profit(prices: Vec<i32>) -> i32 { if prices.len() < 2 { return 0; } let mut profits = vec![0; 2]; let mut max_profit = 0; let mut tmp_min = prices[0]; for i in 1..prices.len() { let (x, y) = (i % 2, (i - 1) % 2); profits[x] = cmp::max(profits[y], prices[i] - tmp_min); tmp_min = cmp::min(tmp_min, prices[i]); max_profit = cmp::max(profits[x], max_profit); } max_profit } }