Leetcode[152] Maximum Product Subarray

_ipo 发布于2019-08-14 16:49 / 1804人阅读

摘要：复杂度思路要保留一个到某一位来看的最大值和最小值。因为在数组中有负数的出现，所以到这一位为止的能得到的最大值，可能是由之前的最大值和这个数相乘得到，也可能是最小值和这个数相乘得到的。

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.

复杂度
O(N),O(1)

思路
要保留一个到某一位来看的最大值和最小值。因为在数组中有负数的出现，所以到这一位为止的能得到的最大值，可能是由之前的最大值和这个数相乘得到，也可能是最小值和这个数相乘得到的。

代码

public int maxProduct(int[] nums) {
    if(nums == null || nums.length == 0) return 0;
    int max = nums[0];
    int maxProduct = nums[0];
    int minProduct = nums[0];
    for(int i = 1; i < nums.length; i ++) {
        int prevMax = maxProduct;
        int prevMin = minProduct;
        maxProduct = Math.max(nums[i], Math.max(prevMax * nums[i], prevMin * nums[i]));
        minProduct = Math.min(nums[i], Math.min(prevMin * nums[i], prevMax * nums[i]));
        max = Math.max(max, maxProduct);
    }
    return max;
}

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

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

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

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
leetcode152 Maximum Product Subarray

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

Arno 2019-08-16 10:57 评论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