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.

Test Cases

Input:

(int[]) nums = [2,3,-2,4]

Output:

(int) 6

Explanation:

[2,3] has the largest product 6.

Solution

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n = nums.size(), l = 0, r = 0, res = nums[0];
        for(int i=0; i<n; i++) {
            l = (l==0 ? 1 : l) * nums[i];
            r = (r==0 ? 1 : r) * nums[n-i-1];
            res = max(res, max(l, r));
        }
        return res;
    }
};
class Solution {
    public int maxProduct(int[] A) {
        int n = A.length, res = A[0], l = 0, r = 0;
        for (int i = 0; i < n; i++) {
            l =  (l == 0 ? 1 : l) * A[i];
            r =  (r == 0 ? 1 : r) * A[n - 1 - i];
            res = Math.max(res, Math.max(l, r));
        }
        return res;
    }
}
class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        rev = nums[::-1]
        for i in range(1, len(nums)):
            nums[i] *= nums[i-1] or 1
            rev[i] *= rev[i-1] or 1
        return max(nums + rev)
Time Complexity: O(n)
Space Complexity: O(1)