152. Maximum Product Subarray

  • 24.8%

https://leetcode.com/problems/maximum-product-subarray/

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

1
2
For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.

方法一:

与52题类似,那个是求和,这个是求积

我的代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
int maxProduct(vector<int>& nums) {
int res = nums[0];
int imin = nums[0], imax = nums[0];
for(int i=1; i<nums.size(); i++){
if(nums[i]<0)
swap(imin, imax);
imin = min(nums[i], nums[i]*imin);
imax = max(nums[i], nums[i]*imax);
res = max(imax, res);
}
return res;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
int maxProduct(vector<int>& nums) {
// store the result that is the max we have found so far
int r = nums[0], n = nums.size();

// imax/imin stores the max/min product of
// subarray that ends with the current number A[i]
for (int i = 1, imax = r, imin = r; i < n; i++) {
// multiplied by a negative makes big number smaller, small number bigger
// so we redefine the extremums by swapping them
if (nums[i] < 0)
swap(imax, imin);

// max/min product for the current number is either the current number itself
// or the max/min by the previous number times the current one
imax = max(nums[i], imax * nums[i]);
imin = min(nums[i], imin * nums[i]);

// the newly computed max value is a candidate for our global result
r = max(r, imax);
}
return r;
}
};

https://discuss.leetcode.com/topic/4417/possibly-simplest-solution-with-o-n-time-complexity

Possibly simplest solution with O(n) time complexity

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int maxProduct(int A[], int n) {
// store the result that is the max we have found so far
int r = A[0];

// imax/imin stores the max/min product of
// subarray that ends with the current number A[i]
for (int i = 1, imax = r, imin = r; i < n; i++) {
// multiplied by a negative makes big number smaller, small number bigger
// so we redefine the extremums by swapping them
if (A[i] < 0)
swap(imax, imin);

// max/min product for the current number is either the current number itself
// or the max/min by the previous number times the current one
imax = max(A[i], imax * A[i]);
imin = min(A[i], imin * A[i]);

// the newly computed max value is a candidate for our global result
r = max(r, imax);
}
return r;
}

my code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
int maxProduct(vector<int>& nums) {
int imax=nums[0], imin=nums[0];
int res=nums[0];
int tmax, tmin;
for(int i=1; i<nums.size(); i++){
tmax = max(imax*nums[i], max(imin*nums[i], nums[i]));
tmin = min(imax*nums[i], min(imin*nums[i], nums[i]));
res = max(tmax, res);
imax = tmax;
imin = tmin;
}
return res;
}
};

python


https://discuss.leetcode.com/topic/22001/in-python-can-it-be-more-concise

In Python, can it be more concise?

1
2
3
4
5
6
def maxProduct(nums):
maximum=big=small=nums[0]
for n in nums[1:]:
big, small=max(n, n*big, n*small), min(n, n*big, n*small)
maximum=max(maximum, big)
return maximum

java


https://discuss.leetcode.com/topic/3607/sharing-my-solution-o-1-space-o-n-running-time

Sharing my solution: O(1) space, O(n) running time

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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;
}

Note:

There’s no need to use O(n) space, as all that you need is a minhere and maxhere. (local max and local min), then you can get maxsofar (which is global max) from them.

There’s a chapter in Programming Pearls 2 that discussed the MaxSubArray problem, the idea is similar.


https://discuss.leetcode.com/topic/5161/simple-java-code

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
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;
}
}

https://discuss.leetcode.com/topic/3581/share-my-dp-code-that-got-ac

Share my DP code that got AC

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
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;
}
}

f[i] means maximum product that can be achieved ending with i

g[i] means minimum product that can be achieved ending with i

谢谢你,可爱的朋友。