2015年7月24日星期五

[LeetCode] Maximum Product Subarray

Problem:

Find the contiguous subarray within an array (containing at least one number) which has the largest product.
For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.

Java Code:

public class Solution {
    public int maxProduct(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        
        int result = nums[0];
        int[] maxProduct = new int[nums.length];
        int[] minProduct = new int[nums.length];
        maxProduct[0] = nums[0];
        minProduct[0] = nums[0];
        
        for (int i = 1; i < nums.length; i++) {
            int[] tmp = new int[3];
            tmp[0] = nums[i];
            tmp[1] = nums[i] * maxProduct[i - 1];
            tmp[2] = nums[i] * minProduct[i - 1];
            
            Arrays.sort(tmp);
            
            result = Math.max(result, tmp[2]);
            maxProduct[i] = tmp[2];
            minProduct[i] = tmp[0];
        }
        
        return result;
    }
}

reference: https://leetcode.com/discuss/41102/share-accepted-dp-java-o-n-solution

没有评论:

发表评论