找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 1080|回复: 2
收起左侧

[米群网刷题小分队] 【LeetCode小分队】【Maximum Product Subarray】-【刷题第一弹】

[复制链接]

14

主题

9

精华

373

积分

高级会员

Rank: 3Rank: 3

积分
373
发表于 10-23-2014 12:46 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 MengMa 于 12-7-2014 12:22 AM 编辑

快速通道:
oj.leetcode.com/problems/maximum-product-subarray/

题目:

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.



建议的回复格式:(如果大家有更好的格式可以补充哦)
思路:(必填)
代码:(必填)
复杂度分析:(必填)
细节和陷阱:(选填)
相似题目:(选填)


=========点击传送门查看所有题目哟========
                            汇总贴 传送门
==================================


思路:
遍利一遍,maxpre 是当前数字之前能得到的最大值,minpre 是当前数字之前能得到的最小值,maxhere 是包含当前节点所能得到的最大值,minhere 是包含当前节点所能得到的最小值。
在对下一数字进行计算前,令 maxpre=maxhere, minpre = minhere,因此由递推可知 maxpre/minpre 中包含的数字与下一个节点总是连续的。

代码:
  1. public class Solution {
  2.     public int maxProduct(int[] A) {
  3.         if(A.length==0)
  4.             return 0;
  5.         int maxhere,minhere;
  6.         int maxpre = A[0];
  7.         int minpre = A[0];
  8.         int maxNow = A[0];
  9.         for(int i=1; i<A.length; i++) {
  10.             maxhere = Math.max(Math.max(maxpre*A【i】, minpre*A【i】), A【i】);
  11.             minhere = Math.min(Math.min(maxpre*A【i】, minpre*A【i】), A【i】);
  12.             maxNow = Math.max(maxNow, maxhere);
  13.             maxpre = maxhere;
  14.             minpre = minhere;
  15.         }
  16.         return maxNow;
  17.     }
  18. }
复制代码


复杂度:
时间-O(n)
空间-O(1)

相似题目:
Largest Sum, Contiguous Subarray
Maximum Subarray

本帖被以下淘专辑推荐:

发表于 10-23-2014 02:48 PM | 显示全部楼层
great post! the MQ points added!
回复 支持 反对

使用道具 举报

14

主题

9

精华

373

积分

高级会员

Rank: 3Rank: 3

积分
373
 楼主| 发表于 10-23-2014 03:48 PM | 显示全部楼层
TeamEditor 发表于 10-23-2014 02:48 PM
great post! the MQ points added!

多谢多谢!
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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