[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 条评论
登录 后参与评论

相关文章

来自专栏我和PYTHON有个约会

26. 企业级开发基础7:面向对象特征(多态)

多态是让我们的程序在运行的过程中,在不同的状态下进行动态的切换,实现复杂的功能为目的的一种程序开发手段

7410
来自专栏知识分享

结构体

数据结构  最慢一星期一章   2015.10.5   一       20:33     首先  我还不知道的一些基础知识 结构体定义并不是定义一个变量,而是...

29460
来自专栏ACM算法日常

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

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

29920
来自专栏Linux Python 加油站

Python基础之set应用详解

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

17650
来自专栏Java与Android技术栈

借助Java 8实现柯里化借助Java 8实现柯里化柯里化的好处总结

在函数式编程中,函数的概念跟数学中函数的概念是一样的,类似于“映射”。高阶函数和柯里化是函数式编程的特性。

17220
来自专栏编程

八大排序算法的 Python 实现!

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

23770
来自专栏深度学习计算机视觉

计算A+B

代码很冗余 时间限制:1秒空间限制:32768K热度指数:347 **算法知识视频讲解 题目描述 给定两个整数A和B,其表示形式是:从个位开始,每三位数用...

29570
来自专栏desperate633

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

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

8210
来自专栏从流域到海域

《Java程序设计基础》 第6章手记

本章主要内容: - 类的定义 - 成员变量和成员方法 - 类及成员的修饰符 - 对象的创建与使用 - 成员变量的访问与方法的...

22250
来自专栏python学习之旅

算法笔记(六):计数排序和基数排序

        这里我是按自己的理解去实现的,时间复杂度和空间复杂度和算法导论上的可能不一样,感兴趣的话参考下就行,感觉最重要的还是算法思想。根据算法性能去实现...

24720

扫码关注云+社区

领取腾讯云代金券