[LeetCode] 152. Maximum Product Subarray

Problem : https://leetcode.com/problems/maximum-product-subarray/

Brute Force ( Time Limit Exceeded )

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        result = nums[0]
        for i in range(len(nums)):
            tmp = nums[i]
            result = max(result, tmp)
            
            for j in range(i+1, len(nums)):
                tmp *= nums[j]
                result = max(result, tmp)
        
        return result

DP Solution:

class Solution {
    public int maxProduct(int[] nums) {
        int miSoFar = nums[0];
        int mxSoFar = nums[0];
        
        int result = nums[0];
        
        for (int i = 1; i < nums.length; i++) {
            int preMiSoFar = miSoFar;
    
            miSoFar = Math.min(mxSoFar * nums[i], Math.min(miSoFar * nums[i], nums[i]));
            mxSoFar = Math.max(preMiSoFar * nums[i], Math.max(mxSoFar * nums[i], nums[i]));
            
            result = Math.max(result, mxSoFar);
        }
        
        return result;
    }
}

Edited on 12/02/2021. Update the DP solution