Tuesday, July 7, 2015

Maximum Product Subarray

Maximum Product Subarray

31%
Accepted
Find the contiguous subarray within an array (containing at least one number) which has the largest product.
Have you met this question in a real interview? 
Yes
Example
For example, given the array [2,3,-2,4], the contiguous subarray [2,3]has the largest product = 6.

public class Solution {
    /**
     * @param nums: an array of integers
     * @return: an integer
     */
    public int maxProduct(int[] nums) {
        // write your code here
       
        int min = nums[0], max = nums[0], product = nums[0];
        for(int i = 1; i < nums.length; i++){
            int maxCopy = max;
            max = Math.max(max*nums[i], Math.max(min*nums[i], nums[i]));
            min = Math.min(maxCopy*nums[i], Math.min(min*nums[i], nums[i]));
            product = Math.max(product, max);
        }
        return product;
    }
}

No comments:

Post a Comment