首页 > 代码库 > Maximum Product Subarray
Maximum Product Subarray
https://oj.leetcode.com/problems/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.
解题思路：
这道题一看就是比较典型的动态规划题目。但和前面的max sum subarray相比，更为巧妙。
令子问题dp[i]为A[i]结尾的数组的最大乘积，状态转移方程就是dp[i] = max(A[i] * dp[i - 1], A[i])。不对，这里发现如果A[i]为负数的话，那么dp[i]就不行了，还必须记录一个A[i-1]结尾的数组的最小乘积，于是我们有第二个dp_min[i]。这样从低至上计算下来。
当然，这里完全可以不考虑A[i]的正负情况，直接dp_max[i] = max(A[i] * dp_max[i - 1], A[i], A[i] * dp_min[i - 1])，dp_min的计算同理。代码更为简洁，时间复杂度不变。
public class Solution { public int maxProduct(int[] A) { int[] dp_max = new int[A.length]; int[] dp_min = new int[A.length]; dp_max[0] = A[0]; dp_min[0] = A[0]; int max = A[0]; int min = A[0]; for(int i = 1; i < A.length; i++){ if(A[i] > 0){ dp_max[i] = Math.max(A[i] * dp_max[i - 1], A[i]); dp_min[i] = Math.min(A[i] * dp_min[i - 1], A[i]); } if(A[i] < 0){ dp_max[i] = Math.max(A[i] * dp_min[i - 1], A[i]); dp_min[i] = Math.min(A[i] * dp_max[i - 1], A[i]); } if(A[i] == 0){ dp_max[i] = 0; dp_min[i] = 0; } if(dp_max[i] > max){ max = dp_max[i]; } if(dp_min[i] < min){ min = dp_min[i]; } } return max; }}
Maximum Product Subarray
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。