Find the contiguous subarray within an array (containing at least one number) which has the largest product. Return an integer corresponding to the maximum product possible.
Example :
Input : [2, 3, -2, 4]
Return : 6
Possible with [2, 3]
Solution:
Time/Space: O(n)
public class Solution {
// DO NOT MODIFY THE ARGUMENTS WITH "final" PREFIX. IT IS READ ONLY
public int maxProduct(final int[] A) {
// p[i] = max positive product ending at i
// n[i] = max negative product ending at i
// p[i] = if (A[i] < 0) n[i - 1] * A[i] else p[i - 1] * A[i]
// n[i] = if (A[i] < 0) p[i - 1] * A[i] else n[i - 1] * A[i]
// max(p[i])
if (A == null || A.length == 0) return 0;
int[] p = new int[A.length];
int[] n = new int[A.length];
int max = A[0];
p[0] = A[0];
n[0] = A[0];
for (int i = 1; i < A.length; i ++) {
int val = A[i];
if (val < 0) {
p[i] = n[i - 1] < 0 ? n[i - 1] * val : val;
n[i] = p[i - 1] > 0 ? p[i - 1] * val : val;
} else if (val > 0) {
p[i] = p[i - 1] > 0 ? p[i - 1] * val : val;
n[i] = n[i - 1] < 0 ? n[i - 1] * val : val;
}
max = Math.max(p[i], max);
}
return max;
}
}
class Solution {
public int maxProduct(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int n = nums.length;
int max = Integer.MIN_VALUE;
int[] positive = new int[n];
int[] negative = new int[n];
if (nums[0] > 0) {
positive[0] = nums[0];
} else if (nums[0] < 0) {
negative[0] = nums[0];
}
max = nums[0];
for (int i = 1; i < n; i ++) {
int val = nums[i];
if (val > 0) {
positive[i] = Math.max(val, positive[i - 1] * val);
negative[i] = negative[i - 1] * val;
} else if (val < 0) {
positive[i] = negative[i - 1] * val;
negative[i] = Math.min(positive[i - 1] * val, val);
}
max = Math.max(max, positive[i]);
}
return max;
}
}