max-prod-subarray.md

Links

Leetcode

Expected Output

Maximum product - that is generated by a subarray from a given array

Dry Run

nums = [2, 3, -2, 4]
op: 6

nums = [-2, 3, 4, -1, 0, 2, 3, 1, 4, 0, 4, 6, -1, 4]
op: 24

why do you need prefix & suffix products, isn't only having prefix not enough?
ex:
nums = [2, 3, -2, 0, 4]
    - max prefix prod = 6, 
    - max suffix prod = 4
    - res = 6

nums = [4, 0, -1, 2, 3]
    - max prefix prod = 4, 
    - max suffix prod = 6
    - res = 6

with the second example you can we need suffix also, because input can have negative numbers.

Brute Force I

1. Using 3 pointers, i => [ , j => ], k traverses from [i, j] & product is recorded

class Solution {
    public int maxProduct(int[] nums) {
       int n = nums.length; 
       int maxProd = Integer.MIN_VALUE;

       for(int i = 0; i < n; i++) {
           for(int j = i; j < n; j++) {
               int prod = 1;
               for(int k = i; k <= j; k++) {
                   prod *= nums[k];
                   maxProd = Math.max(prod, maxProd);
               }
           }
       } 

       return maxProd;
    }
}

T = O(N^3) S = O(1)

Brute Force II

Optimizing brute force 1

1. We only need two pointers, i => [, j => ]
2. prod is used to record the product formed by j's traversal till the end, for each new product formed by formed, gets compared with MaxProd (max prod till now), if greater maxProd gets updated

class Solution {
    public int maxProduct(int[] nums) {
       int n = nums.length; 
       int maxProd = Integer.MIN_VALUE;

       for(int i = 0; i < n; i++) {
           int prod = 1;
           for(int j = i; j < n; j++) {
                prod *= nums[j];
                maxProd = Math.max(prod, maxProd);
           }
       } 

       return maxProd;
    }
}

Optimized

1. pref: records the prefix product & when it encounters a zero, it is reset to 1
2. suff: records the suffix product & when it encounters a zero, it is reset to 1
3. maxProd: records the max product max(maxProd, pref, suff)

Approach

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        pref = 1
        suff = 1
        maxProd = -inf
        n = len(nums)

        for i in range(len(nums)):
            if pref == 0:
                pref = 1

            if suff == 0:
                suff = 1
            
            pref *= nums[i]
            suff *= nums[n - 1 - i]
            
            maxProd = max(maxProd, max(pref, suff))
        
        return maxProd