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.

跟53. Maximum Subarray有点类似，一个是求和一个是求积。需要注意的是，求积的时候两个负数之积为正，所以要考虑最小值

1
2
3
4
5
6
7
8
9
10
11
12
13
public int maxProduct(int[] nums) {
    if (nums == null || nums.length == 0)
        return Integer.MIN_VALUE;
    int maxEndingHere = nums[0], minEndingHere = nums[0], maxSoFar = nums[0];
    for (int i = 1; i < nums.length; i++) {
        int newmaxEndingHere = Math.max(Math.max(nums[i] * maxEndingHere, nums[i] * minEndingHere), nums[i]);
        minEndingHere = Math.min(Math.min(nums[i] * maxEndingHere, nums[i] * minEndingHere), nums[i]);
        maxEndingHere = newmaxEndingHere;
        maxSoFar = Math.max(maxEndingHere, maxSoFar);
    }
    return maxSoFar;
}