[LeetCode] 152. 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.

【解释】 给定一个数组,数组中同时包含正数和负数,求该数组的连续子数组的最大积。 【思路】 这道题比较麻烦的是数组中包含负数的情况,假设给定的数组为[2,3,-2,4],很显然应该返回6(即2 x 3)。若给定数组为[2,3,-2,4,-1],则应该返回48(即数组中所有数想乘)。想象什么情况才可能为最大值,一个是连续正数相乘的情形,还有一种就是负负得正的情形。

第二种情况下,能得到正的最大值只可能是之前负的最大值再乘上一个负数。所以我们不仅要保留当前正数最大值,而且还要保留目前为止的最小值(以防负负得正的情况出现,这里也是看了解析才明白,刚开始还使用记录负数个数的方法试图解决负负得正的问题,看了解析之后才发现自己的代码又长又臭【捂脸】)

public class Solution {
    public int maxProduct(int[] nums) {
     if(nums.length==0) return 0;
        int max=nums[0], min=nums[0];
        int ans=max;
        for(int i=1;i<nums.length;i++){
            int tmpMin=min;
            min=Math.min(nums[i], Math.min(min*nums[i],max*nums[i]));
            max=Math.max(nums[i], Math.max(tmpMin*nums[i], max*nums[i]));
            ans=Math.max(ans, max);//每次保留目前为止的最大值,直接使用max的话,若后面为一个负数,则前面的最大值就会被清洗
        }
        return ans;
        }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏ACM算法日常

基础算法系列之排序算法-3. 直接插入排序

我们之前已经学习了冒泡排序和二分查找两种基本算法,本篇文章我们将一起学习下一个基础算法——直接插入排序算法。

1802
来自专栏Linux Python 加油站

Python基础之set应用详解

一个{ }里面放一些元素就构成了一个集合,set里面可以是多种数据类型(但不能是列表,集合,字典,可以是元组)

1685
来自专栏ACM算法日常

字符串展开(递归)- HDU 1274

常用纱线的品种一般不会超过25种,分别可以用小写字母表示不同的纱线,例如:abc表示三根纱线的排列;重复可以用数字和括号表示,例如:2(abc)表示abcabc...

652
来自专栏人工智能LeadAI

为什么算法容易忘记之插入排序

在学习常用的排序算法时,常有这样的感觉,一看就懂,过眼就忘。原因在于没有将排序的基本思想与代码中各个循环控制变量的意义联系起来进行理解记忆。 插入排序 首先,我...

3485
来自专栏desperate633

[编程题] 奇怪的表达式求值代码

常规的表达式求值,我们都会根据计算的优先级来计算。比如*/的优先级就高于+-。但是小易所生活的世界的表达式规则很简单,从左往右依次计算即可,而且小易所在的世界没...

621
来自专栏令仔很忙

新手学JAVA(六)----处理随机性的数据

在我们的日常生活中会遇到很多随机性的事情,比如:摇奖,彩票,掷色子,这些都可以通过程序计算其中奖的概率。在JAVA的类库中,有一个专门操作这种随机性数据的类—-...

862
来自专栏余林丰

4.比较排序之归并排序(递归)

  归并排序里运用到算法里很重要的一个思想——分治法:将原问题分解为几个规模较小但类似于原问题的子问题——《算法导论》。在每一层递归中都有3个步骤:   1.分...

1908
来自专栏老九学堂

Java微课堂-运算符

Java运算符微视频笔记 赋值运算符 这讲的知识点不多,重点是大家要理解运算符的作用,运算符往往是和变量结合使用,用来解决一些常用的逻辑。比如赋值运算符就是给变...

3487
来自专栏机器学习算法工程师

动态规划系列之最长递增子序列问题解答

今天和大家分享的是动态规划经典问题:最长递增子序列问题解答。(似乎BAT等各大公司都喜欢在面试的时候对动态规划系列经典问题进行笔试。 题目描述: 给定一个整数序...

3137
来自专栏编程

八大排序算法的 Python 实现!

今天CoCo酱给大家介绍一下关于八大排序算法的Python实现,对八大排序算法进行详细描述和代码实现,下面我们一起来看一下吧。 1、插入排序 描述: 插入排序的...

2117

扫码关注云+社区