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

相关文章

来自专栏calmound

KMP专题

POJ 2406 Power Strings http://poj.org/problem?id=2406 题意:找出s字符窜由多少个重复子窜循环构成 分析:K...

2948
来自专栏小二的折腾日记

Leetcode-48-Rotate-Image

这个乍一看觉得不难,但是写的时候又不知道怎么回事,其实旋转,对于我们写程序来说,其实就是不停的调换位置,但是怎么调换是个问题。

652
来自专栏Leetcode名企之路

【Leetcode】59. 螺旋矩阵 II

给定一个正整数 n,生成一个包含 1 到 n2 所有元素,且元素按顺时针顺序螺旋排列的正方形矩阵。

773
来自专栏闵开慧

总结5种比较高效常用的排序算法

1 概述     本文对比较常用且比较高效的排序算法进行了总结和解析,并贴出了比较精简的实现代码,包括选择排序、插入排序、归并排序、希尔排序、快速排序等。算法性...

3487
来自专栏技术碎碎念

LeetCode-53-Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) wh...

27810
来自专栏人工智能LeadAI

为什么算法容易忘记之快速排序

本文用来帮助大家理解记忆快速排序,方法和上篇文章一样,着重理解算法基本思想及其代码中的循环控制变量的意义。 基本思想 快速排序属于拿着元素找位置的算法。思路非常...

3324
来自专栏C语言及其他语言

【编程经验】优秀题解

定义一个数组prime[],赋初值为0,数组下表对应这个数字,通过数组值来判断是否为素数

812
来自专栏尾尾部落

[LeetCode]1-bit and 2-bit Characters 1位和2位字符

链接:https://leetcode.com/problems/1-bit-and-2-bit-characters/description/ 难度:Eas...

631
来自专栏Kevin-ZhangCG

总结五种常见的排序算法

    本文对比较常用且比较高效的排序算法进行了总结和解析,并贴出了比较精简的实现代码,包括选择排序、插入排序、归并排序、希尔排序、快速排序等。算法性能比较如下...

744
来自专栏C语言及其他语言

[每日一题]C语言程序设计教程(第三版)课后习题7.1

题目描述 用简单素数筛选法求N以内的素数。 输入 N 输出 2~N的素数 样例输入 100 样例输出 2 3 5 7 11 13 17 19 23 29 31 ...

3095

扫码关注云+社区