Skip to content

Multiple States I

Description

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

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

Example I:

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

Example II:

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

Questions

  • LeetCode - 152. Maximum Product Subarray

Transform Function

f(k) = Largest product subarray, from index 0 up to k.
g(k) = Smallest product subarray, from index 0 up to k.
f(k) = max( f(k-1) A[k], A[k], g(k-1) A[k] )
g(k) = min( g(k-1) A[k], A[k], f(k-1) A[k] )

Solution

class Solution {
    public int maxProduct(int[] nums) {
        assert nums.length > 0;
        int max = nums[0], min = nums[0], res = nums[0];
        for(int i = 1; i < nums.length; i++) {
            int mx = max, mn = min;
            max = Math.max(Math.max(nums[i], mx * nums[i]), mn * nums[i]);
            min = Math.min(Math.min(nums[i], mx * nums[i]), mn * nums[i]);
            res = Math.max(res, max);
        }
        return res;
    }
}