例题分析 -- 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.

******************************************************************

分析：

    1、特殊情况0，因为0 的相乘特性会使所有的数都变为0，所以在这个题目中会起到隔断作用。可以用一个值来存储历史最大值实时更新

    2、排除了0以后，连续的正数相乘得到的是最大数，如果有负数就可能直接变为最小数，那么也就是说最小数可以变为最大数，最大数也可能变为最小数。

    3、对于局部的最大值，可以从正数开始乘，如果足够大就保存到全局的最大值中。

******************************************************************

代码：

public static int maxProduct(int[] A) {
        if (A == null || A.length == 0)
            return 0;
        if (A.length == 1)
            return A[0];
        int max_local = A[0];
        int min_local = A[0];
        int global = A[0];
        for (int i = 1; i < A.length; i++) {
            int max_copy = max_local;
            // 计算非0段的最大乘积（全是正数，或者 包含偶数个负数）
            max_local = Math.max(Math.max(A[i] * max_local, A[i]), A[i]
                    * min_local);
            // 计算非0段的最小乘积（奇数个负数以及若干个正数）
            min_local = Math.min(Math.min(A[i] * max_copy, A[i]), A[i]
                    * min_local);
            // 保存历史最大乘积值
            global = Math.max(global, max_local);
        }
        return global;
    }