大家好，又见面了，我是全栈君。
LeetCode 新题又更新了。求：最大子数组乘积。
https://oj.leetcode.com/problems/maximum-product-subarray/
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;
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/115679.html原文链接：https://javaforall.net
