LeetCode 152 - Maximum Product Subarray

作者 QIFAN 日期 2017-01-10
LeetCode 152 - Maximum Product Subarray

原题链接: 152. Maximum Product Subarray


题干

给定一个数组,返回该数组连续元素的能产生的最大乘积。

思路

这样一个数组可以看成是正数、负数与 0 的搭配。

我用了一个十分老土的办法,正序算一遍,倒序算一遍。避免了 ‘-2,-3,-4’ 算出 6 而不是 12 的情况。

代码:

public int maxProduct(int[] nums) {
// 正序
int[] res = new int[nums.length];
// 倒序
int[] resReverse = new int[nums.length];
int max = Integer.MIN_VALUE;
// 遇到负数时累积的负数乘积,1 表示之前都是正数,0 表示上一个是 0 或者是第一个负数
int breakPoint = 0;
int breakPointReverse = 0;
for (int pos = 0; pos < nums.length; pos++) {
breakPoint = cal(res, breakPoint, nums[pos], pos);
breakPointReverse = cal(resReverse, breakPointReverse, nums[nums.length - 1 - pos], pos);
max = Math.max(max, Math.max(res[pos], resReverse[pos]));
}
return max;
}
public int cal(int[] res, int breakPoint, int num, int pos) {
// 如果是 0 ,则前后的结果不再有影响
if (num == 0) {
res[pos] = 0;
breakPoint = 0;
// 如果大于 0 且前面都是正数,继续乘
} else if (num > 0 && breakPoint == 1) {
res[pos] = res[pos - 1] * num;
// 如果前面是隔断,则重新开始
} else if (num > 0 && breakPoint == 0) {
res[pos] = num;
breakPoint = 1;
// 如果前面有负数乘积
} else if (num > 0 && breakPoint < 0) {
res[pos] = res[pos - 1] * num;
breakPoint *= num;
// 如果数字小于 0 且之前没有负数
} else if (num < 0 && breakPoint == 1) {
res[pos] = num;
breakPoint = num * res[pos - 1];
// 如果数字小于 0 且前面是隔断
} else if (num < 0 && breakPoint == 0) {
res[pos] = num;
breakPoint = num;
// 如果数字小于 0 且前面有累积的负数乘积
} else {
res[pos] = breakPoint * num;
breakPoint = 1;
}
return breakPoint;
}

Can we do better?

Yes 。既然只用到了前一位,那就不用一整个数组了,只需要留个变量。