05 August 2008
Given an integer array 1
nums
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.
这题和上一题53 - Maximum Subarray非常类似，一个是求最大和，而这个是求最大乘积。可以用大致类似的思路解，只是求乘积比求和要复杂些，因为多了不少corner cases。当然那这题出得还算仁慈，因为这题其实有两个地方简化了：
1）注意这里的数组是整型的，如果含有浮点数，就有可能出现0-1之间类似0.25这样的小数，所以即使是全都是正数，也可以越乘越小。如果数组里的数字全为正数还好说，因为可以用求对数的方式把求乘积转化为求和，从而转换为之前的Maximum Subarray。但是因为这题有负数和0的存在，所以求对数的方法行不通。
2）这题的测试用例里数组元素的绝对值都非常的小，而实际中如果真的连乘起来，最后数值越界很容易发生的。如果考虑这一点，要么估计得用类似Java里BigInteger类这样的东西去避免越界。
所以如同上面一样，在遍历过程中，不断更新以当前元素为终点的subarray的乘积极大值（下面简称极大值）和最大值。本质上无非就是要做出一个二选一：要么继续把当前遍历的元素算上，扩展当前的subarray，要么就重新开始一个subarray。此外，如何更新最大值？由于有整数，负数和0的存在，需要分为三种情况，并且还需要维护一个极小值。为了方便连乘操作，因为都是整数，这里规定维护的最大乘积必须大于等于1，即不能等于0。另外需要注意，在没有遍历到负数之前，极小值这里其实和极大值是一样大的（不考虑为0的情况），也可以是正数。
综合考虑如下：
1）如果当前元素为正数，那么极大值只可能扩大，所以应该继续扩展当前subarray：
此种情况简单，极大值应该更新为原极大值乘以当前元素，极小值更新为原极小值乘以当前元素。全局最大值跟极大值比较。
2）如果当前元素为负数，那么极大值可能会变小，所以不清楚应该继续扩展当前subarray还是新起一个subarray：
对于极大值的更新：如果扩展当前subarray，极大值为原极小值乘以当前元素；如果另外新起一个subarray，由于当前元素为负数，所以直接舍弃，根据规定，设为初始值1。由于这里原极小值不一定为负数，所以前者和后者之间比较没有绝对的谁大。
对于极小值的更新：如果扩展当前subarray，极小值为原极大值乘以当前元素；如果另外新起一个subarray，极小值为当前元素。不过由于之前极大值肯定大于1，所以_当前元素乘以原先的极大值_肯定比_当前元素本身_大，所以极小值更新为原极大值乘以当前元素。
最应该小心的地方是更新全局最大值：这里的全局最大值不能和极大值比较，而应该和极小值乘以当前元素值比较，即扩展当前subarray的选择比较。因为如果极大值此时为1，则并不是靠实实在在存在的，以当前元素结尾的subarray获得，而是靠舍弃当前元素，寄希望于之后“可能”出现的新subarray。举个例子，如果数组为{-2}，或者{-1, 0, -2}，那么无论如何是不会出现最大值为1这种情况的，因为负数的后面没有出现过正数。
3）如果当前元素为0，那么包括一个0会使得极大值成为0，而按照操作规定，这里的极大值应该大于等于1，所以应该舍弃当前元素，新起一个subarray。
对于极大值和极小值，由于新起一个subarray，全部还原为1。
对于全局最大值的更新，这里和2）类似。由于极大值的获取是寄希望于之后“可能”出现的新subarray，所以更新全局最大值的时候不能和此时的极大值1进行比较，而应该和实实在在的0比较。
DP解法，思路跟53题的做法一样，使用滚动数组，只是corner cases更多，获得dp[i]的值只需要dp[i-1]的值，所以是不需要保存整个DP表的。这样一来，DP可以用滚动数组进行优化空间。简单的写法其实就是设一对prevMin/prevMax表示上一个值，以及还有一对curMin/curMax表示当前值。
Time：O(n)；Space：O(1)。
滚动数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public int maxProduct(int[] nums) {
int maxProduct = nums[0], temp = 0;
for (int i = 1, max = maxProduct, min = maxProduct; i < nums.length; i++) {
if (nums[i] < 0) {
temp = min;
min = max;
max = temp;
}
max = Math.max(nums[i], max * nums[i]);
min = Math.min(nums[i], min * nums[i]);
maxProduct = Math.max(maxProduct, max);
}
return maxProduct;
}
}
DP的解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public int maxProduct(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int len = nums.length;
long[] dpP = new long[len];
long[] dpN = new long[len];
dpP[0] = nums[0];
dpN[0] = nums[0];
long result = dpP[0];
for (int i = 1; i < len; i++) {
dpP[i] = Math.max(Math.max(dpP[i - 1] * nums[i], dpN[i - 1] * nums[i]), nums[i]);
dpN[i] = Math.min(Math.min(dpP[i - 1] * nums[i], dpN[i - 1] * nums[i]), nums[i]);
result = Math.max(result, Math.max(dpP[i], dpN[i]));
}
return (int)result;
}
}
状态压缩
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
26
27
28
29
30
31
32
33
34
35
36
// class Solution {
// public int maxProduct(int[] nums) {
// int max = nums[0];
// int prevMin = nums[0], prevMax = nums[0];
// int curMin, curMax;
// for (int i = 1; i < nums.length; i++) {
// curMin = Math.min(Math.min(prevMax * nums[i], prevMin * nums[i]), nums[i]);
// curMax = Math.max(Math.max(prevMax * nums[i], prevMin * nums[i]), nums[i]);
// prevMin = curMin;
// prevMax = curMax;
// max = Math.max(curMax, max);
// }
// return max;
// }
// }
class Solution {
public int maxProduct(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int len = nums.length;
int curMin = Integer.MAX_VALUE;
int curMax = Integer.MIN_VALUE;
int preMin = 1;
int preMax = 1;
int result = nums[0];
for (int num : nums) {
curMin = Math.min(Math.min(preMin * num, preMax * num), num);
curMax = Math.max(Math.max(preMin * num, preMax * num), num);
preMin = curMin;
preMax = curMax;
result = Math.max(result, curMax);
}
return result;
}
}