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

相关文章

来自专栏King_3的技术专栏

leetcode-771-Jewels and Stones(建立哈希表,降低时间复杂度)

2804
来自专栏专注研发

1833 深坑 TLE 求解

题目描述:  大家知道,给出正整数n,则1到n这n个数可以构成n!种排列,把这些排列按照从小到大的顺序(字典顺序)列出,如n=3时,列出1 2 3,1 3 2,...

722
来自专栏smy

js或者php浮点数运算产生多位小数的理解

image.png <?php $f = 0.58; var_dump(intval($f * 100)); //为啥输出57 ?>  首先我...

2959
来自专栏数据结构与算法

洛谷P1887 乘积最大3

题目描述 请你找出M个和为N的正整数,他们的乘积要尽可能的大。 输出字典序最小的一种方案。 输入输出格式 输入格式: 一行,两个正整数N,M 输出格式: M个...

3238
来自专栏武培轩的专栏

剑指Offer-连续子数组的最大和

题目描述 在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边...

2612
来自专栏专注数据中心高性能网络技术研发

[LeetCode]Array主题系列{35,39,40,48题}

1. 内容介绍 开一篇文章记录在leetcode中array主题下面的题目和自己的思考以及优化过程,具体内容层次按照{题目,分析,初解,初解结果,优化解,优化解...

3108
来自专栏xiaoxi666的专栏

和为0的最长连续子数组【转载+优化代码】

题目描述和思路来自博客:http://www.cnblogs.com/coding-wtf/p/5849222.html,在此表示感谢。

422
来自专栏desperate633

LintCode 矩阵的之字型遍历题目分析代码

给你一个包含 m x n 个元素的矩阵 (m 行, n 列), 求该矩阵的之字型遍历。

581
来自专栏King_3的技术专栏

leetcode-485-Max Consecutive Ones

1355
来自专栏算法channel

机器学习|二分法迭代求零点

01 — 二分法求解 对于区间 [a,b] 上单调连续,且 f(a)· f(b)< 0 的函数 y = f(x),通过不断地把函数 f(x)的零点所在的区间一...

3327

扫码关注云+社区