大家好,又见面了,我是全栈君。
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; } }
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115679.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...