Maximum Product Subarray

ztxiong2151049

注册一亩三分地论坛，查看更多干货！

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

昨天晚上发现的新题，搜一下类似解法，然后今天早上研究出来了，应该会有更好地方法，看到再更新吧。我把我借鉴别人修改后的方法放这。

public int maxProduct(int[] A) {
return mp(A, 0, A.length - 1);
}
int mp(int[] a, int l, int r){
if(l > r) return 0;
if(l == r) return a[l];
int noNeg = 0; //数从 l 到 r 有多少个负数
int zeroIndex = -1; //0 出现的位置
for(int i = l; i <= r; i++) {
if(a[i] < 0)
noNeg++;
if(a[i] == 0)
zeroIndex = i;
}
if(zeroIndex >= 0) { //把array 分成左右两部分递归
int left = mp(a, l, zeroIndex - 1);
int right = mp(a, zeroIndex + 1, r);
int tmp = Math.max(left, right); //处理左右两边的结果是负数的情况
return Math.max(0, tmp);
}
if(noNeg % 2 == 0) {
int product = 1;
for (int i = l; i <= r; ++i) {
product *= a[i];
}
return product;
}
int fi, bi; // forward and backward indices
int fp = 1, bp = 1; // forward and backward products
for (fi = l; fi <= r; fi++) {
fp *= a[fi];
if (a[fi] < 0) {
break;
}
}
for(bi = r; bi >= l; bi--) {
bp *= a[bi];
if (a[bi] < 0) {
break;
}
}
int product = 1;
int pbegin = (fp > bp) ? fi + 1 : l; //如果左边乘积大，实际抵消负号后结果反而小，所以取后面部分
int pend = (fp > bp) ? r : bi - 1;
//我们只需要排除一个负号的subarray，因为其他情况的乘积由于element 数量小因而其乘积一定比product小
for (int i = pbegin; i <= pend; ++i) {
product *= a[i];
}
return product;
}

复制代码

时间复杂度：应该是O(n log n)

damajia

本帖最后由 damajia 于 2014-9-25 03:25 编辑

就是普通的 DP 不明白为什么写这么长

class Solution {
public:
int maxProduct(int A[], int n) {
int ret = A[0], mini = A[0], maxn = A[0];
for (int i = 1; i < n; ++i) {
int a = min(mini * A[i], maxn * A[i]);
int b = max(mini * A[i], maxn * A[i]);
mini = min(A[i], a);
maxn = max(A[i], b);
ret = max(ret, maxn);
}
return ret;
}
};

复制代码

[i][/i]

Interviwer

我也用的DP ，时间为O(n),

class Solution {
public:
int maxProduct(int A[], int n) {
vector<vector<int> > product;
for(int i = 0; i < n; i ++) {
vector<int> oneRow(2, 0);
product.push_back(oneRow);
}
// product[i][0] 用A[i] 结尾，乘积为正数最大的
// product[i][1] 用A[i] 结尾，乘积为负数最小的
if(A[0] >= 0) {
product[0][0] = A[0];
}else {
product[0][1] = A[0];
}
bool isZero = false;
for(int i = 1; i < n; i ++) {
if(A[i] > 0) {
if(product[i-1][0] != 0) {
product[i][0] = product[i-1][0] * A[i];
}else {
product[i][0] = A[i];
}
if(product[i-1][1] != 0) {
product[i][1] = product[i-1][1] * A[i];
}
}else if(A[i] < 0){
if(product[i-1][0] != 0) {
product[i][1] = product[i-1][0] * A[i];
}else {
product[i][1] = A[i];
}
if(product[i-1][1] != 0) {
product[i][0] = product[i-1][1] * A[i];
}
}else {
isZero = true;
product[i][0] = 0;
product[i][1] = 0;
}
}
int rst = 0;
for(int i = 0; i < n; i ++) {
rst = max(rst, product[i][0]);
}
if(rst == 0 && isZero == false) {
rst = INT_MIN;
for(int i = 0; i < n; i ++) {
rst = max(rst, product[i][1]);
}
return rst;
}else {
return rst;
}
}
};

复制代码

yuanyin

Leetcode出来了一道新题，大家都是磨刀霍霍，哈哈哈。
分享一下我想的算法，应该是O(n)，搭楼主便车请大家帮忙看看还有什么可改进的地方。

class Solution {
public:
int maxProduct(int A[], int n) {
if (A == NULL || n <= 0)
return 0;
int maxProduct = INT_MIN, maxSoFar = 1, minSoFar = 1;
for (int i = 0; i < n; ++i) {
if (A[i] > 0) {
maxSoFar *= A[i];
minSoFar *= A[i];
maxProduct = max(maxSoFar, maxProduct);
} else if (A[i] == 0) {
maxProduct = max(0, maxProduct);
maxSoFar = 1;
minSoFar = 1;
} else {
maxProduct = max(minSoFar * A[i], maxProduct);
int tmp = maxSoFar;
maxSoFar = max(1, minSoFar * A[i]);
minSoFar = tmp * A[i];
}
}
return maxProduct;
}
};

复制代码

yzl232

damajia 发表于 2014-9-25 02:59
就是普通的 DP 不明白为什么写这么长

牛逼。不到10行

yuanyin

damajia 发表于 2014-9-25 02:59
就是普通的 DP 不明白为什么写这么长

哈哈哈，赞！

ztxiong2151049

就是普通的 DP 不明白为什么写这么长

高端！

xixihaha2014

http://orzorz.me/learn/lesson.htm?courseId=4&lessonId=20 这里讲了两种解法

Argons

本帖最后由 Argons 于 2014-9-26 14:37 编辑

发个python的：

def maxProduct(self, A):
if not A: return 0
if len(A) == 1: return A[0]
curPos, curNeg, curMax = 1, 1, 0
for a in A:
if a > 0:
curPos, curNeg = max(a, curPos*a), curNeg*a
curMax = max(curMax, curPos)
elif a < 0:
curPos, curNeg = curNeg*a, min(a, curPos*a)
curMax = max(curMax, curPos)
else: curPos, curNeg = 1, 1
return curMax

复制代码

nano

贴一下我的，其实这道题感觉和candy很像，因为全部是整数，相对比自然数要简单很多，不考虑零的话乘积的绝对值是一直扩大的，所以要对付的就是负数的个数，为偶数时可以忽略，为奇数时考虑舍弃最左边第一个负数以左
的乘积，和舍弃最右边第一个负数以右的乘积

int maxProduct(int A[], int n)
{
      int max_prod=INT_MIN;
      int prod=1;

      for(int i=0;i<n;i++)
      {
         prod*=A[i];
         max_prod=max(max_prod,prod);
         if(A[i]==0)
         prod=1;
      }

      prod=1;
      for(int i=n-1;i>=0;i--)
      {
         prod*=A[i];
         max_prod=max(max_prod,prod);
         if(A[i]==0)
         prod=1;
      }

      return max_prod;
}

[Leetcode] Maximum Product Subarray

注册一亩三分地论坛，查看更多干货！

相关帖子

评分