152. Maximum Product Subarray

LintCode Array Dynamic Programming

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

Example 1:

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

Example 2:

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

分析

这道题目非常像LeetCode 53. Maximum Subarray，在Q53中给出连续子数组的最大和，这里要求给出连续子数组的最大乘积。所以想办法把kadane算法改编一下。但是这里的整数可能是负数，也就是说原先为负最小的乘积，在乘以一个负数以后，可能会变最大乘积值。所以还要计算连续子数组的最小乘积。

public int maxProduct(int[] nums) {
    if (nums == null) return 0;
    int  maxSoFar = nums[0], maxEndingHere = nums[0];
    int minSoFar = nums[0], minEndingHere = nums[0];
    int prevMaxEndingHere;
    for (int i = 1; i < nums.length; i++) {
        prevMaxEndingHere = maxEndingHere;
        maxEndingHere = Math.max(minEndingHere*nums[i], 
            Math.max(maxEndingHere*nums[i], nums[i]));
        minEndingHere = Math.min(prevMaxEndingHere*nums[i], 
            Math.min(minEndingHere*nums[i], nums[i]));
        maxSoFar = Math.max(maxSoFar, maxEndingHere);
        minSoFar = Math.min(minSoFar, minEndingHere);
    }
    return maxSoFar;        
}