Leetcode Maximum Product Subarray problem solution

YASH PAL,

In this Leetcode Maximum Product Subarray problem solution we have Given an integer array nums, find a contiguous non-empty subarray within the array that has the largest product, and return the product. It is guaranteed that the answer will fit in a 32-bit integer. A subarray is a contiguous subsequence of the array.

Leetcode Maximum Product Subarray problem solution

Problem solution in Python.

class Solution(object):
    def maxProduct(self, nums):
        res1 = [0 for i in range(len(nums))]
        res2 = [0 for i in range(len(nums))]
        
        if len(nums) == 0:
            return 0
        
        for i in range(len(nums)):
            if i == 0:
                res1[i] = nums[i]
                res2[i] = nums[i]
            else:
                res1[i] = max(nums[i], nums[i]*res1[i-1], nums[i]*res2[i-1])
                res2[i] = min(nums[i], nums[i]*res1[i-1], nums[i]*res2[i-1])
        
        return max(max(res1), max(res2))

Problem solution in Java.

if(nums == null) return 0;
        int min = nums[0], max = nums[0], res = nums[0];
        for (int i=1; i<nums.length; i++) {
            int tempMax = max;
            max = Math.max(Math.max(max * nums[i], min * nums[i]), nums[i]);
            min = Math.min(Math.min(tempMax * nums[i], min * nums[i]), nums[i]);
            res = Math.max(res, max);
        }
        
        return res;

Problem solution in C++.

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        if(nums.empty()) return 0;
        int maxv=nums[0];
        int minv=nums[0];
        int res=nums[0];
        int pre;
        for(int i=1; i<nums.size(); i++){
            pre=maxv;
            maxv=max(max(minv*nums[i],maxv*nums[i]),nums[i]);
            minv=min(min(pre*nums[i],minv*nums[i]),nums[i]);
            res=max(maxv,res);
        }
        return res;
    }
};

Problem solution in C.

typedef struct{
    int max;
    int min;
}product;

int maxProduct(int* nums, int numsSize){
    if(numsSize>0){
        product* table = (product*)malloc(sizeof(product)*numsSize);
        table[numsSize-1].max = nums[numsSize-1];
        table[numsSize-1].min = nums[numsSize-1];
        int temp0, temp1;
        for(int i = numsSize-2;i>=0;--i){
            temp0 = nums[i]*table[i+1].max;
            temp1 = nums[i]*table[i+1].min;
            table[i].max = temp1>(nums[i]>temp0?nums[i]:temp0)?temp1:(nums[i]>temp0?nums[i]:temp0);
            table[i].min = temp1<(nums[i]<temp0?nums[i]:temp0)?temp1:(nums[i]<temp0?nums[i]:temp0);
        }
        int result = table[0].max;
        for(int i =1;i<numsSize;++i) result = result>table[i].max?result:table[i].max;
        free(table);
        return result;
    }
    else return 0;
}

coding problems