题目：
Find the contiguous subarray within an array (containing at least one number) which has the largest product.
For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.
链接： http://leetcode.com/problems/maximum-product-subarray/
题解：
求最大乘积子数组。 依然是用Dynamic Programming的思想，不过这回我们要维护一个max以及一个min。根据nums[i]的符号来决定应该怎样计算就可以了。
Time Complexity - O(n)， Space Complexity - O(1)。
public class Solution {
public int maxProduct(int[] nums) {
if(nums == null || nums.length == 0)
return 0;
int res = nums[0], max = nums[0], min = nums[0];
for(int i = 1; i < nums.length; i++) {
if(nums[i] > 0) {
max = Math.max(nums[i], nums[i] * max);
min = Math.min(nums[i], nums[i] * min);
} else {
int max_copy = max;
max = Math.max(nums[i], nums[i] * min);
min = Math.min(nums[i], nums[i] * max_copy);
}
res = Math.max(res,max);
}
return res;
}
}
二刷:
一刷肯定没好好做，直接拷贝答案了吧....导致如今没什么大印象。
下面代码写得比较糙，没有加上overflow和underflow的处理。
- 这里我们对这道题目，先创建一个global max = Integer.MIN_VALUE，一个保存当前正数最大值的posMax = 1和一个保存当前负数最小值的negMax = 1。
- 接下来我们开始从0遍历数组。主要考虑三种情况， 当前num 大于，小于，等于 0。
- 当num > 0的时候，我们直接将posMax和negMax与 num相乘，然后尝试更新max
- 当num < 0的时候，我们先设置一个tmp = posMax。
- 在当前negMax < 0的时候
- 我们可以更新posMax = negMax * max， 负负得正
- 更新negMax = tmp * num， 即negMax为之前的posMax * num
- 尝试更新max = Math.max(max, posMax)
- 否则negMax > 0
- 因为num是负数，所有我们更新posMax = 1
- 更新negMax *= num
- 尝试更新 max = Math.max(max, num)， 即max跟当前数字进行比较
- 在当前negMax < 0的时候
- 我们更新posMax = 1, negMax = 1
- 尝试更新 max = Math.max(max, num)。 即max跟当前数字比较， 因为当前数字num = 0，所以也可以直接写 Math.max(max, 0)。
当num == 0的时候，这时候之前cache的乘积都断了
- 返回结果max。
写得比较繁杂，应该可以简化不少。留给下一次了。 参观了一下Discuss区，大神们写得好棒好巧妙...收录在reference里。 下回再写的时候要参考写出简单的代码。
Java:
public class Solution {
public int maxProduct(int[] nums) {
if (nums == null || nums.length == 0) return 0;
int max = Integer.MIN_VALUE;
int posMax = 1, negMax = 1;
for (int num : nums) {
if (num > 0) {
posMax *= num;
negMax *= num;
max = Math.max(max, posMax);
} else if (num < 0) {
if (negMax < 0) {
int tmp = posMax;
posMax = negMax * num;
negMax = tmp * num;
max = Math.max(max, posMax);
} else {
posMax = 1;
negMax *= num;
max = Math.max(max, num);
}
} else {
posMax = 1;
negMax = 1;
max = Math.max(max, num);
}
}
return max;
}
}
来自mzchen大神的swap做法，好巧妙:
这里我们跟上面一样维护一个min和一个max，以及一个global的结果res。每次当nums[i] < 0的时候，我们swap一下min和max。在一般情况下，我们更新
max = Math.max(nums[i], max * nums[i])， min = Math.min(nums[i], min * nums[i])，这两个步骤可以处理nums[i] = 0的case。最后我们尝试更新res = Math.max(res, max)。
Java:
public class Solution {
public int maxProduct(int[] nums) {
if (nums == null || nums.length == 0) return 0;
int res = nums[0];
int max = nums[0], min = nums[0];
for (int i = 1; i < nums.length; i++) {
if (nums[i] < 0) {
int tmp = max;
max = min;
min = tmp;
}
max = Math.max(nums[i], max * nums[i]);
min = Math.min(nums[i], min * nums[i]);
res = Math.max(res, max);
}
return res;
}
}
Update:
public class Solution {
public int maxProduct(int[] nums) {
if (nums == null || nums.length == 0) return 0;
int max = 1, min = 1;
int res = Integer.MIN_VALUE;
for (int num : nums) {
if (num < 0) {
int tmp = max;
max = min;
min = tmp;
}
max = Math.max(num, max * num);
min = Math.min(num, min * num);
res = Math.max(res, max);
}
return res;
}
}
Test cases:
[-5, 2, -1, -7]
[-1, 2, 3, -4]
[-5, 2, 0, -1, -7]
[-1, -2, -3, -4]
[0, -5, -2, -1, 7]
[-2]
[2]
[-2, -2, -2, -2]
[Integer.MAX_VALUE, Integer.MIN_VALUE, Integer.MIN_VALUE, Integer.MIN_VALUE] <- 这个没有测
Reference：
https://leetcode.com/discuss/11923/sharing-my-solution-o-1-space-o-n-running-time
https://leetcode.com/discuss/14235/possibly-simplest-solution-with-o-n-time-complexity
https://leetcode.com/discuss/19795/share-my-c-solution-maybe-is-the-simplest-solution
https://leetcode.com/discuss/16238/simple-java-code
https://leetcode.com/discuss/64079/my-concise-dp-o-n-java-solution-with-o-1-extra-space