首页 > 代码库 > LeetCode Maximum Product Subarray 解题报告

LeetCode Maximum Product Subarray 解题报告

LeetCode 新题又更新了,最大子数组乘积
https://oj.leetcode.com/problems/maximum-product-subarray/

题目分析:求一个数组,连续子数组的最大乘积。
解题思路:最简单的思路就是3重循环,求解productArray[i][j]的值(productArray[i][j]为A[i]到A[j]的乘积),然后记录其中最大值,算法时间复杂度O(n3),必然TLE。

第一次优化,动态规划,求解:productArray[i][j]的时候不用再次循环从i到j,而是利用:productArray[i][j]=productArray[i][j-1]*A[j];采用递推的方法来计算,算法时间复杂度为O(n2),遗憾的是也TLE了。
public class Solution {
    public int maxProduct(int A[]) {
        if(A==null||A.length==0) {
	      return 0;
	    }
	    int[][] productArray =  new int[A.length][A.length];
	    int maxProduct = A[0];
	    
	    for(int i=0;i<A.length;i++) {
	    	for(int j=i;j<A.length;j++) {
	    		if(j==i) {
	    		    productArray[i][i] = A[i];
	    		} else {
	    		    productArray[i][j] = productArray[i][j-1]*A[j];
	    		}
	    		if(productArray[i][j]>maxProduct) {
	    			maxProduct = productArray[i][i];
	    		}
	    	}
	    }
	    return maxProduct;
    }
}

第二次优化,其实子数组乘积最大值的可能性为:累乘的最大值碰到了一个正数;或者,累乘的最小值(负数),碰到了一个负数。所以每次要保存累乘的最大(正数)和最小值(负数)。同时还有一个选择起点的逻辑,如果之前的最大和最小值同当前元素相乘之后,没有当前元素大(或小)那么当前元素就可作为新的起点。例如,前一个元素为0的情况,{1,0,9,2},到9的时候9应该作为一个最大值,也就是新的起点,{1,0,-9,-2}也是同样道理,-9比当前最小值还小,所以更新为当前最小值。
这种方法只需要遍历一次数组即可,算法时间复杂度为O(n)。

public class Solution {
    public int maxProduct(int A[]) {
        if(A==null||A.length==0) {
	      return 0;
	    }
	    int maxProduct = A[0];
	    int max_temp   = A[0];
	    int min_temp   = A[0];
	    
	    for(int i=1;i<A.length;i++) {
	    	int a = A[i]*max_temp;
	    	int b = A[i]*min_temp;
	    	max_temp = Math.max(Math.max(a,b), A[i]);
	    	min_temp = Math.min(Math.min(a,b), A[i]);
	    	maxProduct = Math.max(maxProduct, max_temp);
	    }
	    return maxProduct;
    }
}









LeetCode Maximum Product Subarray 解题报告