首页 > 代码库 > [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.
Solution:
本题要点在于不仅要维护一个局部最大值，还要维护一个局部最小值。
这道题跟Maximum Subarray模型上和思路上都比较类似，还是用一维动态规划中的“局部最优和全局最优法”。这里的区别是维护一个局部最优不足以求得后面的全局最优，这是由于乘法的性质不像加法那样，累加结果只要是正的一定是递增，乘法中有可能现在看起来小的一个负数，后面跟另一个负数相乘就会得到最大的乘积。不过事实上也没有麻烦很多，我们只需要在维护一个局部最大的同时，在维护一个局部最小，这样如果下一个元素遇到负数时，就有可能与这个最小相乘得到当前最大的乘积和，这也是利用乘法的性质得到的。
1 public class Main { 2 3 public static void main(String[] args) { 4 Main so = new Main(); 5 int[] A = { 2, 1, -2, 4 }; 6 System.out.println(so.maxProduct(A)); 7 } 8 9 public int maxProduct(int[] A) {10 if (A == null || A.length == 0)11 return 0;12 if (A.length == 1)13 return A[0];14 int max_local = A[0];15 int min_local = A[0];16 int global = A[0];17 for (int i = 1; i < A.length; ++i) {18 int max_copy = max_local;19 // max_local = Math.max(A[i] * max_copy, A[i] * min_local);20 // min_local = Math.min(A[i] * max_copy, A[i] * min_local);21 max_local=Math.max(Math.max(A[i], A[i]*max_copy), A[i]*min_local);22 min_local=Math.min(Math.min(A[i], A[i]*max_copy), A[i]*min_local);23 global = Math.max(max_local, global);24 }25 return global;26 }27 }
需要注意的一点是：在比较的时候需要将(A[i])(A[i]*max_copy)以及(A[i]*min_local)三个一起进行比较，才能达到取得局部最佳的效果。
[Leetcode] Maximum Product Subarray
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。