public class Solution {
/**
* @param nums: an array of integers
* @return: an integer
*/
public int maxProduct(int[] nums) {
int[] max = new int[nums.length]; // maximum product ending with nums[i]
int[] min = new int[nums.length]; // minimum product ending with nums[i]
max[0] = min[0] = nums[0];
int result = max[0];
for (int i = 1; i < nums.length; i++) {
max[i] = min[i] = nums[i];
if (nums[i] > 0) { // 区分nums[i]的符号
max[i] = Math.max(max[i], nums[i] * max[i - 1]);
min[i] = Math.min(min[i], nums[i] * min[i - 1]);
} else {
max[i] = Math.max(max[i], nums[i] * min[i - 1]);
min[i] = Math.min(min[i], nums[i] * max[i - 1]);
}
result = Math.max(max[i], result);
}
return result;
}
}
DP - Simplified - O(n) space, O(1) time
class Solution {
public int maxProduct(int[] nums) {
if (nums == null || nums.length == 0) return 0;
int n = nums.length;
int[] maxProduct = new int[n]; // max subarray product ending in nums[i]
int[] minProduct = new int[n]; // min subarray product ending in nums[i]
maxProduct[0] = nums[0];
minProduct[0] = nums[0];
int max = maxProduct[0];
for (int i = 1; i < n; i++) {
maxProduct[i] = Math.max(nums[i], Math.max(maxProduct[i - 1] * nums[i], minProduct[i - 1] * nums[i]));
minProduct[i] = Math.min(nums[i], Math.min(maxProduct[i - 1] * nums[i], minProduct[i - 1] * nums[i]));
max = Math.max(maxProduct[i], max);
}
return max;
}
}
DP, improved, with O(1) space, O(n) time
public class Solution {
/**
* @param nums: an array of integers
* @return: an integer
*/
public int maxProduct(int[] nums) {
int result, currentMax, currentMin;
result = currentMax = currentMin = nums[0];
for (int i = 1; i < nums.length; i++) {
int temp = currentMax;
currentMax = Math.max(nums[i], Math.max(currentMax * nums[i], currentMin * nums[i]));
currentMin = Math.min(nums[i], Math.min(temp * nums[i], currentMin * nums[i]));
result = Math.max(currentMax, result);
}
return result;
}
}
O(1) space, O(n) time
class Solution {
public int maxProduct(int[] nums) {
if (nums == null || nums.length == 0){
return 0;
}
int maxPre = nums[0], minPre = nums[0], max = nums[0], maxHere, minHere;
for (int i = 1; i < nums.length; i++){
maxHere = Math.max(nums[i], Math.max(nums[i] * maxPre, nums[i] * minPre));
minHere = Math.min(nums[i], Math.min(nums[i] * maxPre, nums[i] * minPre));
max = Math.max(max, maxHere);
maxPre = maxHere;
minPre = minHere;
}
return max;
}
}
Same idea but a more concise implementation
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;
}