[−][src]Function leetcode_for_rust::cd0152_maximum_product_subarray::max_product
pub fn max_product(nums: 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; impl Solution { pub fn max_product(nums: Vec<i32>) -> i32 { if nums.len() == 0 { return 0; } let mut dp = vec![vec![0; 2]; 2]; // dp[x][0] max value, dp[x][1] min value let mut result = nums[0]; dp[0][0] = nums[0]; dp[0][1] = nums[0]; for i in 1..nums.len() { let (x, y) = (i % 2, (i - 1) % 2); // x, y is 0 or 1 if nums[i] >= 0 { dp[x][0] = cmp::max(dp[y][0] * nums[i], nums[i]); dp[x][1] = cmp::min(dp[y][1] * nums[i], nums[i]); } else { dp[x][0] = cmp::max(dp[y][1] * nums[i], nums[i]); dp[x][1] = cmp::min(dp[y][0] * nums[i], nums[i]); } // simplify if else like this // dp[x][0] = vec![dp[y][0] * nums[i], dp[y][1] * nums[i], nums[i]].iter().max().unwrap().clone(); // dp[x][1] = vec![dp[y][0] * nums[i], dp[y][1] * nums[i], nums[i]].iter().min().unwrap().clone(); result = cmp::max(dp[x][0], result); } result } }
Approach 2: Dynamic Programming
-
Time complexity: O(n)
-
Space complexity: O(1)
-
Runtime: 0 ms
-
Memory: 2.5 MB
impl Solution { pub fn max_product(nums: Vec<i32>) -> i32 { if nums.is_empty() { return 0; } let mut cur_max = nums[0]; let mut cur_min = nums[0]; let mut result = nums[0]; for &num in nums[1..].into_iter() { if num >= 0 { cur_max = i32::max(cur_max * num, num); cur_min = i32::min(cur_min * num, num); } else { let tmp = cur_max; cur_max = i32::max(cur_min * num, num); cur_min = i32::min(tmp * num, num); } result = i32::max(cur_max, result); } result } }
Approach 3: Dynamic Programming
-
Time complexity: O(n)
-
Space complexity: O(1)
-
Runtime: 0 ms
-
Memory: 2.5 MB
use std::mem; use std::cmp; impl Solution { pub fn max_product(nums: Vec<i32>) -> i32 { let mut min = nums[0]; let mut max = nums[0]; let mut res = nums[0]; for i in 1..nums.len() { if nums[i] < 0 { mem::swap(&mut min, &mut max); } min = cmp::min(nums[i], min*nums[i]); max = cmp::max(nums[i], max*nums[i]); res = cmp::max(res, max); } return res; } }