Difficulty: Medium
Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.
Example 1:
1
2
3
| Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.
|
Example 2:
1
2
3
| Input: [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
|
Solution
Language: Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| 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;
}
}
|