一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 4101|回复: 16
收起左侧

[Leetcode] Maximum Product Subarray

[复制链接] |试试Instant~ |关注本帖
ztxiong2151049 发表于 2014-9-24 23:15:00 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
昨天晚上发现的新题,搜一下类似解法,然后今天早上研究出来了,应该会有更好地方法,看到再更新吧。我把我借鉴别人修改后的方法放这。
  1. public int maxProduct(int[] A) {
  2.         return mp(A, 0, A.length - 1);
  3.     }
  4.     int mp(int[] a, int l, int r){
  5.         if(l > r) return 0;
  6.         if(l == r) return a[l];
  7.         int noNeg = 0;  //数从 l 到 r 有多少个负数
  8.         int zeroIndex = -1; //0 出现的位置
  9.         for(int i = l; i <= r; i++) {
  10.             if(a[i] < 0)
  11.                 noNeg++;
  12.             if(a[i] == 0)
  13.                 zeroIndex = i;
  14.         }
  15.         if(zeroIndex >= 0) { //把array 分成左右两部分递归
  16.             int left = mp(a, l, zeroIndex - 1);
  17.             int right = mp(a, zeroIndex + 1, r);
  18.             int tmp = Math.max(left, right); //处理左右两边的结果是负数的情况
  19.                     return Math.max(0, tmp);
  20.         }
  21.         if(noNeg % 2 == 0) {
  22.             int product = 1;
  23.                         for (int i = l; i <= r; ++i) {
  24.                                 product *= a[i];
  25.                         }
  26.                         return product;
  27.         }
  28.         int fi, bi; // forward and backward indices
  29.                 int fp = 1, bp = 1; // forward and backward products
  30.                 for (fi = l; fi <= r; fi++) {
  31.                         fp *= a[fi];
  32.                         if (a[fi] < 0) {
  33.                                 break;
  34.                         }
  35.                 }
  36.                 for(bi = r; bi >= l; bi--) {
  37.                         bp *= a[bi];
  38.                         if (a[bi] < 0) {
  39.                                 break;
  40.                         }
  41.                 }
  42.                
  43.                 int product = 1;
  44.                 int pbegin = (fp > bp) ? fi + 1 : l; //如果左边乘积大,实际抵消负号后结果反而小,所以取后面部分
  45.                 int pend = (fp > bp) ? r : bi - 1;
  46.                 //我们只需要排除一个负号的subarray,因为其他情况的乘积由于element 数量小因而其乘积一定比product小
  47.                 for (int i = pbegin; i <= pend; ++i) {
  48.                         product *= a[i];
  49.                 }
  50.                 return product;
  51.     }
复制代码
时间复杂度:应该是O(n log n)
damajia 发表于 2014-9-25 02:59:26 | 显示全部楼层
本帖最后由 damajia 于 2014-9-25 03:25 编辑

就是普通的 DP 不明白为什么写这么长
  1. class Solution {
  2. public:
  3.   int maxProduct(int A[], int n) {
  4.     int ret = A[0], mini = A[0], maxn = A[0];
  5.     for (int i = 1; i < n; ++i) {
  6.       int a = min(mini * A[i], maxn * A[i]);
  7.       int b = max(mini * A[i], maxn * A[i]);
  8.       mini = min(A[i], a);
  9.       maxn = max(A[i], b);
  10.       ret = max(ret, maxn);
  11.     }
  12.     return ret;
  13.   }
  14. };
复制代码

评分

2

查看全部评分

回复 支持 3 反对 1

使用道具 举报

yuanyin 发表于 2014-9-24 23:43:32 | 显示全部楼层
Leetcode出来了一道新题,大家都是磨刀霍霍,哈哈哈。
分享一下我想的算法,应该是O(n),搭楼主便车请大家帮忙看看还有什么可改进的地方。
  1. class Solution {
  2. public:
  3.     int maxProduct(int A[], int n) {
  4.         if (A == NULL || n <= 0)
  5.             return 0;
  6.             
  7.         int maxProduct = INT_MIN, maxSoFar = 1, minSoFar = 1;
  8.         for (int i = 0; i < n; ++i) {
  9.             if (A[i] > 0) {
  10.                 maxSoFar *= A[i];
  11.                 minSoFar *= A[i];
  12.                 maxProduct = max(maxSoFar, maxProduct);
  13.             } else if (A[i] == 0) {
  14.                 maxProduct = max(0, maxProduct);
  15.                 maxSoFar = 1;
  16.                 minSoFar = 1;
  17.             } else {
  18.                 maxProduct = max(minSoFar * A[i], maxProduct);
  19.                 int tmp = maxSoFar;
  20.                 maxSoFar = max(1, minSoFar * A[i]);
  21.                 minSoFar = tmp * A[i];
  22.             }
  23.         }
  24.         
  25.         return maxProduct;
  26.     }
  27. };
复制代码
回复 支持 反对

使用道具 举报

Interviwer 发表于 2014-9-25 01:14:39 | 显示全部楼层
我也用的DP , 时间为O(n),
  1. class Solution {
  2. public:
  3.     int maxProduct(int A[], int n) {
  4.         vector<vector<int> > product;
  5.         for(int i = 0; i < n; i ++) {
  6.             vector<int> oneRow(2, 0);
  7.             product.push_back(oneRow);
  8.         }
  9.         // product[i][0] 用A[i] 结尾,乘积为正数最大的
  10.         // product[i][1] 用A[i] 结尾,乘积为负数最小的
  11.         if(A[0] >= 0) {
  12.             product[0][0] = A[0];
  13.         }else {
  14.             product[0][1] = A[0];
  15.         }
  16.         bool isZero = false;
  17.         for(int i = 1; i < n; i ++) {
  18.             if(A[i] > 0) {
  19.                 if(product[i-1][0] != 0) {
  20.                     product[i][0] = product[i-1][0] * A[i];
  21.                 }else {
  22.                     product[i][0] = A[i];
  23.                 }
  24.                
  25.                 if(product[i-1][1] != 0) {
  26.                     product[i][1] = product[i-1][1] * A[i];
  27.                 }
  28.             }else if(A[i] < 0){
  29.                 if(product[i-1][0] != 0) {
  30.                     product[i][1] = product[i-1][0] * A[i];
  31.                 }else {
  32.                     product[i][1] = A[i];
  33.                 }
  34.                
  35.                 if(product[i-1][1] != 0) {
  36.                     product[i][0] = product[i-1][1] * A[i];
  37.                 }
  38.             }else {
  39.                 isZero = true;
  40.                 product[i][0] = 0;
  41.                 product[i][1] = 0;
  42.             }
  43.         }
  44.         
  45.         int rst = 0;
  46.         for(int i = 0; i < n; i ++) {
  47.             rst = max(rst, product[i][0]);
  48.         }
  49.         if(rst == 0 && isZero == false) {
  50.             rst = INT_MIN;
  51.             for(int i = 0; i < n; i ++) {
  52.                 rst = max(rst, product[i][1]);
  53.             }
  54.             return rst;
  55.         }else {
  56.             return rst;
  57.         }
  58.     }
  59. };
复制代码
回复 支持 反对

使用道具 举报

yzl232 发表于 2014-9-25 03:41:39 | 显示全部楼层
damajia 发表于 2014-9-25 02:59
就是普通的 DP 不明白为什么写这么长

牛逼。 不到10行
回复 支持 反对

使用道具 举报

yuanyin 发表于 2014-9-25 04:41:06 | 显示全部楼层
damajia 发表于 2014-9-25 02:59
就是普通的 DP 不明白为什么写这么长

哈哈哈,赞!
回复 支持 反对

使用道具 举报

 楼主| ztxiong2151049 发表于 2014-9-25 05:32:10 | 显示全部楼层
就是普通的 DP 不明白为什么写这么长

高端!
回复 支持 反对

使用道具 举报

xixihaha2014 发表于 2014-9-25 21:26:48 | 显示全部楼层
回复 支持 反对

使用道具 举报

Argons 发表于 2014-9-26 14:30:49 | 显示全部楼层
本帖最后由 Argons 于 2014-9-26 14:37 编辑

发个python的:
  1.     def maxProduct(self, A):
  2.         if not A: return 0
  3.         if len(A) == 1: return A[0]
  4.         curPos, curNeg, curMax = 1, 1, 0
  5.         for a in A:
  6.             if a > 0:
  7.                 curPos, curNeg = max(a, curPos*a), curNeg*a
  8.                 curMax = max(curMax, curPos)
  9.             elif a < 0:
  10.                 curPos, curNeg = curNeg*a, min(a, curPos*a)
  11.                 curMax = max(curMax, curPos)
  12.             else: curPos, curNeg = 1, 1
  13.         return curMax
复制代码
回复 支持 反对

使用道具 举报

nano 发表于 2014-10-8 08:58:55 | 显示全部楼层
贴一下我的,其实这道题感觉和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;
    }
回复 支持 反对

使用道具 举报

averillzheng 发表于 2014-10-9 11:29:14 | 显示全部楼层
就是简单的dp问题。
回复 支持 反对

使用道具 举报

285845348 发表于 2014-10-17 12:06:44 | 显示全部楼层
class Solution:
    def maxProduct(self, A):
        ps, ns = [A[0]], [A[0]]
        for i in xrange(1, len(A)):
            tp, tn = ps[-1], ns[-1]
            ps.append(max(A[i], A[i] * tp, A[i] * tn))
            ns.append(min(A[i], A[i] * tn, A[i] * tp))
        return max(ps)
回复 支持 反对

使用道具 举报

quan1614 发表于 2014-11-18 10:02:26 | 显示全部楼层
damajia 发表于 2014-9-25 02:59
就是普通的 DP 不明白为什么写这么长

你写的答案错了,自己到leetcodeOJ上提交一遍,自己在看看吧
回复 支持 反对

使用道具 举报

GLambda 发表于 2014-11-25 01:19:51 | 显示全部楼层
O(n)的,想法是最大值 = 最小负值 * 最小负值,或者是最大正值 * 最大正值。最小负值 = 最大正值 * 最小负值
  1. class Solution {
  2. public:
  3.     int maxProduct(int A[], int n) {
  4.         vector<int> maxdp(n), mindp(n);
  5.         
  6.         maxdp[0] = mindp[0] = A[0];
  7.         int maxv = maxdp[0];
  8.         for (int i = 1; i < n; i++) {
  9.             maxdp[i] = max(mindp[i - 1] * A[i], maxdp[i - 1] * A[i]);
  10.             maxdp[i] = max(maxdp[i], A[i]);
  11.             mindp[i] = min(mindp[i - 1] * A[i], maxdp[i - 1] * A[i]);
  12.             mindp[i] = min(mindp[i], A[i]);
  13.             maxv = max(maxv, maxdp[i]);
  14.         }
  15.         return maxv;
  16.     }
  17. };
复制代码
回复 支持 反对

使用道具 举报

chong 发表于 2014-12-23 20:28:27 | 显示全部楼层
quan1614 发表于 2014-11-17 20:02
你写的答案错了,自己到leetcodeOJ上提交一遍,自己在看看吧

我觉得他写的是对的啊。同时保存局部最小和最大,保存最小是用乘法的负负得正的规律决定的。
回复 支持 反对

使用道具 举报

quan1614 发表于 2015-12-26 17:55:34 | 显示全部楼层
chong 发表于 2014-12-23 20:28
我觉得他写的是对的啊。同时保存局部最小和最大,保存最小是用乘法的负负得正的规律决定的。

maxProduct要求是连续的,它只保留了历史上最大最小的,没有保留当前临时最大最小的。
或者简单点说,这种做法不能保证得到的是连续区间的,所以错了
我邮箱 dongjiaquan89@gmail.com 可以私下说
回复 支持 反对

使用道具 举报

traderalg 发表于 2016-1-6 12:24:10 | 显示全部楼层
O(N) algorithm:

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n = nums.size();
        if(n<=0) return 0;
        int ret, curMax, curMin;
        ret = curMax = curMin = nums[0];
        for(int i=1; i<n; i++) {
            int temp = curMax;
            curMax = max(max(curMax*nums[i], curMin*nums[i]),nums[i]);
            curMin = min(min(temp*nums[i], curMin*nums[i]),nums[i]);
            ret = max(ret, curMax);
        }
        return ret;
    }
};

回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-7 16:46

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表