152. Maximum Product Subarray Medium

1/**
2 * [152] Maximum Product Subarray
3 *
4 * Given an integer array nums, find a contiguous non-empty subarray within the array that has the largest product, and return the product.
5 * The test cases are generated so that the answer will fit in a 32-bit integer.
6 * A subarray is a contiguous subsequence of the array.
7 *  
8 * Example 1:
9 * 
10 * Input: nums = [2,3,-2,4]
11 * Output: 6
12 * Explanation: [2,3] has the largest product 6.
13 * 
14 * Example 2:
15 * 
16 * Input: nums = [-2,0,-1]
17 * Output: 0
18 * Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
19 * 
20 *  
21 * Constraints:
22 * 
23 * 1 <= nums.length <= 2 * 10^4
24 * -10 <= nums[i] <= 10
25 * The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
26 * 
27 */
28pub struct Solution {}
29
30// problem: https://leetcode.com/problems/maximum-product-subarray/
31// discuss: https://leetcode.com/problems/maximum-product-subarray/discuss/?currentPage=1&orderBy=most_votes&query=
32
33// submission codes start here
34use std::cmp;
35impl Solution {
36    pub fn max_product(nums: Vec<i32>) -> i32 {
37        let mut max = nums[0];
38        let mut min = nums[0];
39        let mut result = nums[0];
40
41        for i in 1..nums.len() {
42            let nmax = cmp::max(min * nums[i], cmp::max(max * nums[i], nums[i]));
43            min = cmp::min(min * nums[i], cmp::min(max * nums[i], nums[i]));
44            max = nmax;
45            result = cmp::max(result, max)
46        }
47        result
48    }
49}
50
51// submission codes end
52
53#[cfg(test)]
54mod tests {
55    use super::*;
56
57    #[test]
58    fn test_152() {
59        assert_eq!(Solution::max_product(vec![2,3,-2,4]), 6)
60    }
61}
62