152. Maximum Product Subarray (Dynamic Programming) 20.2.19 Medium

Given an integer array nums, find the contiguous subarray within an array 
(containing at least one number) which has the largest product.

Example 1:

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

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


Solution: ------------------------------------ Dynamic Programming ----------------------- https://www.youtube.com/watch?v=AtzfZHb35YI
---------------------------------------------- O(n) T, O(1) S
class Solution(object):
    def maxProduct(self, nums):                                   # Very similar to 53. Maximum Subarray
                                                                  # Only difference is that, the product may become greater if - * -
                                                                  # So, in here, we introduce another variable "currmin"
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0
        currmax, currmin, res = nums[0], nums[0], nums[0]         # res is set to nums[0] for cases like [-2], 
                                                                  # where the for loop will not be executed
        for i in range(1, len(nums)):
            currmax, currmin = max(currmax * nums[i], currmin * nums[i], nums[i]), min(currmax * nums[i], currmin * nums[i], nums[i])
            '''
            IMPORTANT  !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
            Why we cannot divide it into two lines like:
            currmax = max(currmax * nums[i], currmin * nums[i], nums[i])
            currmin = min(currmax * nums[i], currmin * nums[i], nums[i]) ?????????????????????????????????????
            Because for the second line, the currmax has already been updated to the new currmax,
            but what we want is the currmax in the previous iteration
            '''
            res = max(res, currmax)
        return res


Java Version:
class Solution {
    public int maxProduct(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int currMax = nums[0], currMin = nums[0], res = nums[0];
        for (int i = 1; i < nums.length; i ++) {
            int tempMax = currMax, temMin = currMin;
            currMax = Math.max(Math.max(tempMax * nums[i], temMin * nums[i]), nums[i]);
            currMin = Math.min(Math.min(tempMax * nums[i], temMin * nums[i]), nums[i]);
            res = Math.max(currMax, res);
        }
        
        return res;
    }
}