首页 > 代码库 > [LeetCode]Maximum Product Subarray

[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.

动态规划

public class Solution {
    public int maxProduct(int[] A) {
        assert A.length>0;
        int max = A[0],min = A[0],res = A[0];
        for(int i= 1;i<A.length;i++){
        	int mx = max ,mn = min;
        	max = Math.max(Math.max(mx*A[i], A[i]),mn*A[i]);
        	min = Math.min(Math.min(mx*A[i], A[i]),mn*A[i]);
        	res = Math.max(res, max);
        }
        return res;
    }
}




[LeetCode]Maximum Product Subarray