leetcode152 Maximum Product Subarray

Arno 发布于2019-08-16 10:57 / 1966人阅读

摘要：题目要求从一个整数数组中找到一个子数组，该子数组中的所有元素的乘积最大。比如数组的最大乘积子数组为思路与代码这题目考察了动态编程的思想。至于为什么还要比较，是因为如果是一个负数的，那么之前的最小乘积在这里可能就成为了最大的乘积了。

题目要求

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]的最大乘积子数组为[2,3]

思路与代码

这题目考察了动态编程的思想。从一个更高的视角看这个问题，我们可以推理一下，假如我们知道了以第i位为结尾的子数组的最大乘积值和最小乘积值，我们能否知道第(i+1)位的最大乘积值和最小乘积值呢？答案是肯定的。因为只需要比较max( nums[i+1], maxProduct[i]*nums[i+1], minProduct[i]*nums[i+1])就可以了。
至于为什么还要比较minProduct[i]*nums[i+1]，是因为如果nums[i+1]是一个负数的，那么之前的最小乘积在这里可能就成为了最大的乘积了。

代码如下：

    public int maxProduct(int[] nums) {
        //记录在遍历过程中所得到的最大乘积值
        int max = nums[0];
        for(int i = 1, curMax = max, curMin = max ; i

想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~

GPU云服务器云服务器 subarray Maximum Leetcod Product

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/70775.html

Leetcode[152] Maximum Product Subarray

摘要：复杂度思路要保留一个到某一位来看的最大值和最小值。因为在数组中有负数的出现，所以到这一位为止的能得到的最大值，可能是由之前的最大值和这个数相乘得到，也可能是最小值和这个数相乘得到的。 Leetcode[152] Maximum Product Subarray Find the contiguous subarray within an array (containing at le...

_ipo 2019-08-14 16:49 评论0 收藏0
leetcode-152-Maximum Product Subarray

摘要：问题本质本质动态规划问题。局部最优，全局最优。乘法问题，存在的情况是负数或者正数，或者从当前数开始新的连续元素相乘可能发生的情况在某个节点，继续之前的增大减小，从此节点转折。所以只要在局部动态中，保持最大最小当前，进行判断保留即可。 Given an integer array nums, find the contiguous subarray within an array (co...

thursday 2019-07-30 17:32 评论0 收藏0
[LintCode/LeetCode] Maximum Product Subarray

摘要：这是一道简单的动规题目，同步更新数组解决了为负数的问题。即使是求最小乘积子序列，也可以通过取和的最小值获得。 Problem Find the contiguous subarray within an array (containing at least one number) which has the largest product. Example For example, g...

meteor199 2019-08-14 15:21 评论0 收藏0
leetcode 部分解答索引（持续更新～）

摘要：前言从开始写相关的博客到现在也蛮多篇了。而且当时也没有按顺序写现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新前言从开始写leetcode相关的博客到现在也蛮多篇了。而且当时也没有按顺序写～现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理 1~50 1...

leo108 2019-08-15 14:26 评论0 收藏0
[LeetCode] Maximum Size Subarray Sum Equals k

Problem Given an array nums and a target value k, find the maximum length of a subarray that sums to k. If there isnt one, return 0 instead. Note The sum of the entire nums array is guaranteed to fit ...

MudOnTire 2019-08-15 15:47 评论0 收藏0