Maximum Product Subarray

昨天晚上发现的新题，搜一下类似解法，然后今天早上研究出来了，应该会有更好地方法，看到再更新吧。我把我借鉴别人修改后的方法放这。

public int maxProduct(int[] A) {[br][br][/br]        return mp(A, 0, A.length - 1);[br][/br][br][/br]    }[br][/br][br][/br]    int mp(int[] a, int l, int r){[br][br][/br]        if(l > r) return 0;[br][/br][br][/br]        if(l == r) return a[l];[br][/br][br][/br]        int noNeg = 0;  //数从 l 到 r 有多少个负数[br][/br][br][/br]        int zeroIndex = -1; //0 出现的位置[br][/br][br][/br]        for(int i = l; i <= r; i++) {[br][/br][br][/br]            if(a[i] < 0)[br][/br][br][/br]                noNeg++;[br][/br][br][/br]            if(a[i] == 0)[br][/br][br][/br]                zeroIndex = i;[br][/br][br][/br]        }[br][/br][br][/br]        if(zeroIndex >= 0) { //把array 分成左右两部分递归[br][/br][br][/br]            int left = mp(a, l, zeroIndex - 1);[br][/br][br][/br]            int right = mp(a, zeroIndex + 1, r);[br][/br][br][/br]            int tmp = Math.max(left, right); //处理左右两边的结果是负数的情况[br][/br][br][/br]		    return Math.max(0, tmp);[br][/br][br][/br]        }[br][/br][br][/br]        if(noNeg % 2 == 0) {[br][/br][br][/br]            int product = 1;[br][/br][br][/br]			for (int i = l; i <= r; ++i) {[br][/br][br][/br]				product *= a[i];[br][/br][br][/br]			}[br][/br][br][/br]			return product;[br][/br][br][/br]        }[br][/br][br][/br]        int fi, bi; // forward and backward indices[br][/br][br][/br]		int fp = 1, bp = 1; // forward and backward products[br][/br][br][/br]		for (fi = l; fi <= r; fi++) {[br][/br][br][/br]			fp *= a[fi];[br][/br][br][/br]			if (a[fi] < 0) {[br][/br][br][/br]				break;[br][/br][br][/br]			}[br][/br][br][/br]		}[br][/br][br][/br]		for(bi = r; bi >= l; bi--) {[br][/br][br][/br]			bp *= a[bi];[br][/br][br][/br]			if (a[bi] < 0) {[br][/br][br][/br]				break;[br][/br][br][/br]			}[br][/br][br][/br]		}[br][/br][br][/br]		[br][/br][br][/br]		int product = 1;[br][/br][br][/br]		int pbegin = (fp > bp) ? fi + 1 : l; //如果左边乘积大，实际抵消负号后结果反而小，所以取后面部分[br][/br][br][/br]		int pend = (fp > bp) ? r : bi - 1;[br][/br][br][/br]		//我们只需要排除一个负号的subarray，因为其他情况的乘积由于element 数量小因而其乘积一定比product小[br][/br][br][/br]		for (int i = pbegin; i <= pend; ++i) {[br][/br][br][/br]			product *= a[i];[br][/br][br][/br]		}[br][/br][br][/br]		return product;[br][/br][br][/br]    }时间复杂度：应该是O(n log n)[/i][/i][/i][/i]