Problem statement

Given an integer array nums, find a contiguous non-empty subarray within the array that has the largest product, and return the product.

The test cases are generated so that the answer will fit in a 32-bit integer.

A subarray is a contiguous subsequence of the array.
Link to problem

Example 1

Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

Example 2

Input: nums = [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.Input: nums = [1]

Solutions

Approach 1: Quadratic

Exactly what we did in the previous problem, except we use sum instead of product. This is also optimized to use just two loops instead of the usual 3.

Implementation in Rust

fn max_psubarray(numbers: Vec<i32>) -> i32 {
    let mut max_product = numbers[0];
    for i in 0..numbers.len() {
        let mut product = 1;
        for j in i..numbers.len() {
            product *= numbers[j];
            if product > max_product {
                max_product = product;
            }
        }
    }
    max_product
}

Time Complexity: $O(n^2)$
Runtime on LeetCode: $280$ms

Approach 2: Dynamic Programming

This approach was quite a challenge to come up with and I wouldn’t have been able to come up with this if I hadn’t watched NeetCode,s video.

You not only track the maximum but also the minimum.
While you’re iterating over the elements, you determine the maximum and the minimum and see what element multiplied by minimum or maximum gives the maximum value.

Pseudocode

set cur_max, cur_min, global_max to numbers[0]

begin loop
    is current element > 0 ?
        cur_max = max of [numbers[i] * cur_max, numbers[i]]
        cur_min = min of [numbers[i] * cur_min, numbers[i]]
    or is current element < 0 ?
        cur_max = max of [numbers[i] * cur_min, numbers[i]]
        cur_min = min of [numbers[i] * old_cur_max, numbers[i]]
    or is current element 0 ?
        cur_max = cur_min = 0
    
    global_max = max of [global_max, cur_max]

Brief explanation of the pseudocode:

current element > 0 We check if the current element is greater than 0, which means that upon multiplying either the max or min, we will get the direct maximum or minimum. There is not much to think about here, multiply current number by max and you get a new max, multiply current number by min and you get a new min.

current element < 0
Essentially, what we are trying to do here is: What do you get when you multiply two negative numbers? You get a big positive number! What do you get when you multiply a negative number and a positive number? You get a big negative number!

More explanation if the above was not sufficient
is the current number multiplied by the minimum the highest? if so then that will be our new maximum, else our current number will be the maximum.
Is the current number multiplied by the maximum the lowest (why the lowest? because negative multiplied by positive will yield negative)? if so then that will be our new minimum, else our current number will be the minimum.

Implementation in Rust

fn max_psubarray(numbers:Vec<i32>) -> i32 {
    let mut cur_max = numbers[0];
    let mut cur_min = numbers[0];
    let mut global_max = numbers[0];

    for i in 1..numbers.len() {
        if numbers[i] > 0 {
            cur_max = std::cmp::max(numbers[i] * cur_max, numbers[i]);
            cur_min = std::cmp::min(numbers[i] * cur_min, numbers[i]);
        } else if numbers[i] < 0 {
            let tmp_cur_max = cur_max;
            cur_max = std::cmp::max(numbers[i] * cur_min, numbers[i]);
            cur_min = std::cmp::min(numbers[i] * tmp_cur_max, numbers[i]);
        } else {
            cur_max = 0;
            cur_min = 0;
        }
        global_max = std::cmp::max(global_max, cur_max);
    }
    global_max
}

Time Complexity: $O(n)$
Runtime on LeetCode: $0$ms