Alibi

My Life is Getting Better

Leetcode[152] Maximum Product Subarray

13 Nov 2015

###Task1 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.

###Python

class Solution(object):
    def maxProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums or len(nums) == 0:
            return 0
        glob = nums[0]
        locMin = nums[0]
        locMax = nums[0]
        for num in nums[1:]:
            
            locMinTemp = locMin
            locMin = min(num, locMin * num, locMax * num)
            locMax = max(num, locMax * num, locMinTemp * num)
            glob = max(glob, locMax)
        return glob

###Java

public class Solution {
    public int maxProduct(int[] nums) {
        //brute force
        if (nums == null || nums.length == 0) {
        	return 0;
        }

        int global = nums[0];
        int localMin = nums[0];
        int localMax = nums[0];
        for (int i = 1; i < nums.length; i++) {
            int temp = localMax;
            localMax = Math.max(Math.max(localMax * nums[i], nums[i]), localMin * nums[i]);
            localMin = Math.min(Math.min(localMin * nums[i], nums[i]), temp * nums[i]);
            global = Math.max(global, localMax);
        }

        return global;
    }
    public static void main(String[] args) {
    	Solution sol = new Solution();
    	int[] nums = {2, 3, -2, 4};
    	System.out.println(sol.maxProduct(nums));
    }
}

###Points

这道题跟Maximum Subarray模型上和思路上都比较类似，还是用一维动态规划中的“局部最优和全局最优法”。这里的区别是维护一个局部最优不足以求得后面的全局最优，这是由于乘法的性质不像加法那样，累加结果只要是正的一定是递增，乘法中有可能现在看起来小的一个负数，后面跟另一个负数相乘就会得到最大的乘积。不过事实上也没有麻烦很多，我们只需要在维护一个局部最大的同时，在维护一个局部最小，这样如果下一个元素遇到负数时，就有可能与这个最小相乘得到当前最大的乘积和，这也是利用乘法的性质得到的

Related Posts