https://leetcode.com/problems/maximum-product-subarray/
X. https://leetcode.com/problems/maximum-product-subarray/discuss/48330/Simple-Java-code
https://leetcode.com/problems/maximum-product-subarray/discuss/48261/Share-my-DP-code-that-got-AC
Maximum Product Subarray: Given an array that contains both positive and negative integers, find the product of the maximum product subarray. Expected Time complexity is O(n) and only O(1) extra space can be use
It is similar to Largest Sum Contiguous Subarray problem. The only thing to note here is, maximum product can also be obtained by minimum (negative) product ending with the previous element multiplied by this element.
The solution works for all cases mentioned above. It doesn’t work for arrays like {0, 0, -20, 0}, {0, 0, 0}.. etc. The solution can be easily modified to handle this case.
O(1) space:
http://www.programcreek.com/2014/03/leetcode-maximum-product-subarray-java/
When iterating the array, each element has two possibilities: positive number or negative number. We need to track a minimum value, so that when a negative number is given, it can also find the maximum value. We define two local variables, one tracks the maximum and the other tracks the minimum.
Java Version: http://www.jiuzhang.com/solutions/maximum-product-subarray/
TODO
http://www.programcreek.com/2014/03/leetcode-maximum-product-subarray-java/
GoLang:
https://github.com/Max-Liu/Leetcode-in-golang/blob/master/maximum-product-subarray/main.go
func main() {
array := []int{4, 5, -4, 2, 2, 8}
fmt.Println(maximumProductSubarray(array))
}
func maximumProductSubarray(array []int) int {
var maxEndingHere, minEndingHere, maxSoFar int = 1, 1, 1
for key, _ := range array {
switch {
case array[key] > 0:
{
maxEndingHere = maxEndingHere * array[key]
minEndingHere = min(minEndingHere*array[key], 1)
}
case array[key] == 0:
{
maxEndingHere = 1
minEndingHere = 1
}
default:
{
temp := maxEndingHere
maxEndingHere = max(minEndingHere*array[key], 1)
minEndingHere = temp * array[key]
}
}
if maxSoFar < maxEndingHere {
maxSoFar = maxEndingHere
}
}
return maxSoFar
}
func max(a, b int) int {
if a < b {
return b
}
return a
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
Read full article from Maximum Product Subarray | GeeksforGeeks
Given an integer array
nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.
Example 1:
Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.
Example 2:
Input: [-2,0,-1] Output: 0 Explanation: The result cannot be 2, because [-2,-1] is not a subarray
X. https://leetcode.com/problems/maximum-product-subarray/discuss/48330/Simple-Java-code
Loop through the array, each time remember the max and min value for the previous product, the most important thing is to update the max and min value: we have to compare among max * A[i], min * A[i] as well as A[i], since this is product, a negative * negative could be positive.
public int maxProduct(int[] A) {
if (A == null || A.length == 0) {
return 0;
}
int max = A[0], min = A[0], result = A[0];
for (int i = 1; i < A.length; i++) {
int temp = max;
max = Math.max(Math.max(max * A[i], min * A[i]), A[i]);
min = Math.min(Math.min(temp * A[i], min * A[i]), A[i]);
if (max > result) {
result = max;
}
}
return result;
}public int maxProduct(int[] A) {
if (A.length == 0) {
return 0;
}
int maxherepre = A[0];
int minherepre = A[0];
int maxsofar = A[0];
int maxhere, minhere;
for (int i = 1; i < A.length; i++) {
maxhere = Math.max(Math.max(maxherepre * A[i], minherepre * A[i]), A[i]);
minhere = Math.min(Math.min(maxherepre * A[i], minherepre * A[i]), A[i]);
maxsofar = Math.max(maxhere, maxsofar);
maxherepre = maxhere;
minherepre = minhere;
}
return maxsofar;
}https://leetcode.com/problems/maximum-product-subarray/discuss/48261/Share-my-DP-code-that-got-AC
public int maxProduct(int[] A) {
if (A == null || A.length == 0) {
return 0;
}
int[] f = new int[A.length];
int[] g = new int[A.length];
f[0] = A[0];
g[0] = A[0];
int res = A[0];
for (int i = 1; i < A.length; i++) {
f[i] = Math.max(Math.max(f[i - 1] * A[i], g[i - 1] * A[i]), A[i]);
g[i] = Math.min(Math.min(f[i - 1] * A[i], g[i - 1] * A[i]), A[i]);
res = Math.max(res, f[i]);
}
return res;
}
http://www.cnblogs.com/grandyang/p/4028713.htmlf[i] means maximum product that can be achieved ending with ig[i] means minimum product that can be achieved ending with i
这个求最大子数组乘积问题是由最大子数组之和问题演变而来，但是却比求最大子数组之和要复杂，因为在求和的时候，遇到0，不会改变最大值，遇到负数，也只是会减小最大值而已。而在求最大子数组乘积的问题中，遇到0会使整个乘积为0，而遇到负数，则会使最大乘积变成最小乘积，正因为有负数和0的存在，使问题变得复杂了不少。比如，我们现在有一个数组[2, 3, -2, 4]，我们可以很容易的找出所有的连续子数组，[2], [3], [-2], [4], [2, 3], [3, -2], [-2, 4], [2, 3, -2], [3, -2, 4], [2, 3, -2, 4], 然后可以很轻松的算出最大的子数组乘积为6，来自子数组[2, 3].
那么我们如何写代码来实现自动找出最大子数组乘积呢，我最先想到的方比较简单粗暴，就是找出所有的子数组，然后算出每一个子数组的乘积，然后比较找出最大的一个，需要两个for循环，第一个for遍历整个数组，第二个for遍历含有当前数字的子数组，就是按以下顺序找出子数组: [2], [2, 3], [2, 3, -2], [2, 3, -2, 4], [3], [3, -2], [3, -2, 4], [-2], [-2, 4], [4], 我在本地测试的一些数组全部通过，于是兴高采烈的拿到OJ上测试，结果丧心病狂的OJ用一个有15000个数字的数组来测试，然后说我程序的运行时间超过了要求值，我一看我的代码，果然如此，时间复杂度O(n2), 得想办法只用一次循环搞定。我想来想去想不出好方法，于是到网上搜各位大神的解决方法。其实这道题最直接的方法就是用DP来做，而且要用两个dp数组，其中f[i]表示子数组[0, i]范围内并且一定包含nums[i]数字的最大子数组乘积，g[i]表示子数组[0, i]范围内并且一定包含nums[i]数字的最小子数组乘积，初始化时f[0]和g[0]都初始化为nums[0]，其余都初始化为0。那么从数组的第二个数字开始遍历，那么此时的最大值和最小值只会在这三个数字之间产生，即f[i-1]*nums[i]，g[i-1]*nums[i]，和nums[i]。所以我们用三者中的最大值来更新f[i]，用最小值来更新g[i]，然后用f[i]来更新结果res即可，由于最终的结果不一定会包括nums[n-1]这个数字，所以f[n-1]不一定是最终解，不断更新的结果res才是，参见代码如下：
解法一：
class Solution { public: int maxProduct(vector<int>& nums) { int res = nums[0], n = nums.size(); vector<int> f(n, 0), g(n, 0); f[0] = nums[0]; g[0] = nums[0]; for (int i = 1; i < n; ++i) { f[i] = max(max(f[i - 1] * nums[i], g[i - 1] * nums[i]), nums[i]); g[i] = min(min(f[i - 1] * nums[i], g[i - 1] * nums[i]), nums[i]); res = max(res, f[i]); } return res; } };
我们可以对上面的解法进行空间上的优化，以下摘自OJ官方解答，大体思路相同，写法更加简洁：
Besides keeping track of the largest product, we also need to keep track of the smallest product. Why? The smallest product, which is the largest in the negative sense could become the maximum when being multiplied by a negative number.
Let us denote that:
f(k) = Largest product subarray, from index 0 up to k.
Similarly,
g(k) = Smallest product subarray, from index 0 up to k.
Then,
f(k) = max( f(k-1) * A[k], A[k], g(k-1) * A[k] ) g(k) = min( g(k-1) * A[k], A[k], f(k-1) * A[k] )
There we have a dynamic programming formula. Using two arrays of size n, we could deduce the final answer as f(n-1). Since we only need to access its previous elements at each step, two variables are sufficient.
public int maxProduct(int[] A) { assert A.length > 0; int max = A[0], min = A[0], maxAns = A[0]; for (int i = 1; i < A.length; i++) { int mx = max, mn = min; max = Math.max(Math.max(A[i], mx * A[i]), mn * A[i]); min = Math.min(Math.min(A[i], mx * A[i]), mn * A[i]); maxAns = Math.max(max, maxAns); } return maxAns; }
根据上述描述可以写出代码如下：
解法二：
class Solution { public: int maxProduct(vector<int>& nums) { if (nums.empty()) return 0; int res = nums[0], mn = nums[0], mx = nums[0]; for (int i = 1; i < nums.size(); ++i) { int tmax = mx, tmin = mn; mx = max(max(nums[i], tmax * nums[i]), tmin * nums[i]); mn = min(min(nums[i], tmax * nums[i]), tmin * nums[i]); res = max(res, mx); } return res; } };
下面这种方法也是用两个变量来表示当前最大值和最小值的，但是没有无脑比较三个数，而是对于当前的nums[i]值进行了正负情况的讨论：
1. 当遍历到一个正数时，此时的最大值等于之前的最大值乘以这个正数和当前正数中的较大值，此时的最小值等于之前的最小值乘以这个正数和当前正数中的较小值。
2. 当遍历到一个负数时，我们先用一个变量t保存之前的最大值mx，然后此时的最大值等于之前最小值乘以这个负数和当前负数中的较大值，此时的最小值等于之前保存的最大值t乘以这个负数和当前负数中的较小值。
3. 在每遍历完一个数时，都要更新最终的最大值。
P.S. 如果这里改成求最小值的话，就是求最小子数组乘积，并且时间复杂度是醉人的O(n)，是不是很强大呢，参见代码如下：
解法三：
class Solution { public: int maxProduct(vector<int>& nums) { int res = nums[0], mx = res, mn = res; for (int i = 1; i < nums.size(); ++i) { if (nums[i] > 0) { mx = max(mx * nums[i], nums[i]); mn = min(mn * nums[i], nums[i]); } else { int t = mx; mx = max(mn * nums[i], nums[i]); mn = min(t * nums[i], nums[i]); } res = max(res, mx); } return res; } };
下面这道题使用了一个trick来将上面解法的分情况讨论合成了一种，在上面的解法中我们分析了当nums[i]为正数时，最大值和最小值的更新情况，为负数时，稍有不同的就是最小值更新时要用到之前的最大值，而不是更新后的最大值，所以我们才要用变量t来保存之前的结果。而下面这种方法的巧妙处在于先判断一个当前数字是否是负数，是的话就交换最大值和最小值。那么此时的mx就是之前的mn，所以mx的更新还是跟上面的方法是统一的，而在在更新mn的时候，之前的mx已经保存到mn中了，而且并没有改变，所以可以直接拿来用，不得不说，确实叼啊，参见代码如下：
解法四：
class Solution { public: int maxProduct(vector<int>& nums) { int res = nums[0], mx = res, mn = res; for (int i = 1; i < nums.size(); ++i) { if (nums[i] < 0) swap(mx, mn); mx = max(nums[i], mx * nums[i]); mn = min(nums[i], mn * nums[i]); res = max(res, mx); } return res; } };
再来看一种画风不太一样的解法，这种解法遍历了两次，一次是正向遍历，一次是反向遍历，相当于正向建立一个累加积数组，每次用出现的最大值更新结果res，然后再反响建立一个累加积数组，再用出现的最大值更新结果res，注意当遇到0的时候，prod要重置为1。至于为啥正反两次遍历就可以得到正确的结果了呢？主要还是由于负数个数的关系，因为负数可能会把最大值和最小值翻转，那么当有奇数个负数时，如果只是正向遍历的话，可能会出错，比如 [-1, -2, -3]，我们累加积会得到 -1，2，-6，看起来最大值只能为2，其实不对，而如果我们再反向来一遍，累加积为 -3，6，-6，就可以得到6了。所以当负数个数为奇数时，首次出现和末尾出现的负数就很重要，有可能会是最大积的组成数字，所以遍历两次就不会漏掉组成最大值的机会，参见代码如下：
解法五：
class Solution { public: int maxProduct(vector<int>& nums) { int res = nums[0], prod = 1, n = nums.size(); for (int i = 0; i < n; ++i) { res = max(res, prod *= nums[i]); if (nums[i] == 0) prod = 1; } prod = 1; for (int i = n - 1; i >= 0; --i) { res = max(res, prod *= nums[i]); if (nums[i] == 0) prod = 1; } return res; }
Maximum Product Subarray: Given an array that contains both positive and negative integers, find the product of the maximum product subarray. Expected Time complexity is O(n) and only O(1) extra space can be use
It is similar to Largest Sum Contiguous Subarray problem. The only thing to note here is, maximum product can also be obtained by minimum (negative) product ending with the previous element multiplied by this element.
int maxSubarrayProduct(int arr[], int n){ // max positive product ending at the current position int max_ending_here = 1; // min negative product ending at the current position int min_ending_here = 1; // Initialize overall max product int max_so_far = 1; /* Traverse throught the array. Following values are maintained after the ith iteration: max_ending_here is always 1 or some positive product ending with arr[i] min_ending_here is always 1 or some negative product ending with arr[i] */ for (int i = 0; i < n; i++) { /* If this element is positive, update max_ending_here. Update min_ending_here only if min_ending_here is negative */ if (arr[i] > 0) { max_ending_here = max_ending_here*arr[i]; min_ending_here = min (min_ending_here * arr[i], 1); } /* If this element is 0, then the maximum product cannot end here, make both max_ending_here and min_ending_here 0 Assumption: Output is alway greater than or equal to 1. */ else if (arr[i] == 0) { max_ending_here = 1; min_ending_here = 1; } /* If element is negative. This is tricky max_ending_here can either be 1 or positive. min_ending_here can either be 1 or negative. next min_ending_here will always be prev. max_ending_here * arr[i] next max_ending_here will be 1 if prev min_ending_here is 1, otherwise next max_ending_here will be prev min_ending_here * arr[i] */ else { int temp = max_ending_here; max_ending_here = max (min_ending_here * arr[i], 1); min_ending_here = temp * arr[i]; } // update max_so_far, if needed if (max_so_far < max_ending_here) max_so_far = max_ending_here; } return max_so_far;}O(1) space:
http://www.programcreek.com/2014/03/leetcode-maximum-product-subarray-java/
When iterating the array, each element has two possibilities: positive number or negative number. We need to track a minimum value, so that when a negative number is given, it can also find the maximum value. We define two local variables, one tracks the maximum and the other tracks the minimum.
public int maxProduct(int[] A) { if(A==null || A.length==0) return 0; int maxLocal = A[0]; int minLocal = A[0]; int global = A[0]; for(int i=1; i<A.length; i++){ int temp = maxLocal; maxLocal = Math.max(Math.max(A[i]*maxLocal, A[i]), A[i]*minLocal); minLocal = Math.min(Math.min(A[i]*temp, A[i]), A[i]*minLocal); global = Math.max(global, maxLocal); } return global; } |
public int maxProduct(List<Integer> nums) { int[] max = new int[nums.size()]; int[] min = new int[nums.size()]; min[0] = max[0] = nums.get(0); int result = nums.get(0); for (int i = 1; i < nums.size(); i++) { min[i] = max[i] = nums.get(i); if (nums.get(i) > 0) { max[i] = Math.max(max[i], max[i - 1] * nums.get(i)); min[i] = Math.min(min[i], min[i - 1] * nums.get(i)); } else if (nums.get(i) < 0) { max[i] = Math.max(max[i], min[i - 1] * nums.get(i)); min[i] = Math.min(min[i], max[i - 1] * nums.get(i)); } result = Math.max(result, max[i]); } return result; }http://leetcodesolution.blogspot.com/2014/09/leetcode-maximum-product-subarray.html
TODO
int maxProduct(int A[], int n) {int maxProd = INT_MIN;int prod = 1;for(int i=0; i <n; i++){prod = prod * A[i];maxProd = max(maxProd, prod);if (A[i] == 0)prod = 1;}- prod = 1;
for(int i=n-1; i >=0; i--){prod = prod * A[i];maxProd = max(maxProd, prod);if (A[i] == 0)prod = 1;}return maxProd;}
http://www.programcreek.com/2014/03/leetcode-maximum-product-subarray-java/
public int maxProduct(int[] A) { int max = Integer.MIN_VALUE; for(int i=0; i<A.length; i++){ for(int l=0; l<A.length; l++){ if(i+l < A.length){ int product = calProduct(A, i, l); max = Math.max(product, max); } } } return max; } public int calProduct(int[] A, int i, int j){ int result = 1; for(int m=i; m<=j; m++){ result = result * A[m]; } return result; }http://acmerblog.iteye.com/blog/1994364
GoLang:
https://github.com/Max-Liu/Leetcode-in-golang/blob/master/maximum-product-subarray/main.go
func main() {
array := []int{4, 5, -4, 2, 2, 8}
fmt.Println(maximumProductSubarray(array))
}
func maximumProductSubarray(array []int) int {
var maxEndingHere, minEndingHere, maxSoFar int = 1, 1, 1
for key, _ := range array {
switch {
case array[key] > 0:
{
maxEndingHere = maxEndingHere * array[key]
minEndingHere = min(minEndingHere*array[key], 1)
}
case array[key] == 0:
{
maxEndingHere = 1
minEndingHere = 1
}
default:
{
temp := maxEndingHere
maxEndingHere = max(minEndingHere*array[key], 1)
minEndingHere = temp * array[key]
}
}
if maxSoFar < maxEndingHere {
maxSoFar = maxEndingHere
}
}
return maxSoFar
}
func max(a, b int) int {
if a < b {
return b
}
return a
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
Read full article from Maximum Product Subarray | GeeksforGeeks
