leetcode: Maximum Product Subarray

问题描述：

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.

原问题链接：https://leetcode.com/problems/maximum-product-subarray/

 

问题分析

　　这个问题在之前的文章里有过讨论。对于一个连续最大子序列的乘积来说，它满足这么一个条件。这个最大值要么就是这个元素本身，要么就是它当前最大乘积和它的乘积，要么就是它当前最小乘积和它的乘积。因为这个元素为正数的时候，它和最大序列的乘积可能是最大的。而它为负数的时候，它和最小序列的乘积可能是最大的。

　　按照这个思路，我们可以得到详细的实现如下：

 

public class Solution {
    public int maxProduct(int[] nums) {
        int maxCur = nums[0], minCur = nums[0], maxTmp = maxCur, minTmp = minCur, result = nums[0];
        for(int i = 1; i < nums.length; i++) {
            maxTmp = Math.max(nums[i], Math.max(maxCur * nums[i], minCur * nums[i]));
            minTmp = Math.min(nums[i], Math.min(maxCur * nums[i], minCur * nums[i]));
            maxCur = maxTmp;
            minCur = minTmp;
            result = Math.max(result, maxCur);
        }
        return result;
    }
}