[LintCode/LeetCode] Maximum Product Subarray

meteor199 发布于2019-08-14 15:21 / 1212人阅读

摘要：这是一道简单的动规题目，同步更新数组解决了为负数的问题。即使是求最小乘积子序列，也可以通过取和的最小值获得。

Problem

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

Example

For example, given the array [2,3,-2,4], the contiguous subarray [2,3] has the largest product = 6.

Note

这是一道简单的动规题目，同步更新min[]数组解决了nums[i]为负数的问题。即使是求最小乘积子序列，也可以通过取res和min[i]的最小值获得。

Solution

public class Solution {
    public int maxProduct(int[] nums) {
        int len = nums.length;
        int[] max = new int[len];
        int[] min = new int[len];
        int res = max[0] = min[0] = nums[0];
        for (int i = 1; i < len; i++) {
            if (nums[i] >= 0) {
                max[i] = Math.max(nums[i], max[i-1]*nums[i]);
                min[i] = Math.min(nums[i], min[i-1]*nums[i]);
            }
            else {
                max[i] = Math.max(nums[i], min[i-1]*nums[i]);
                min[i] = Math.min(nums[i], max[i-1]*nums[i]);
            }
            res = Math.max(res, max[i]);
        }
        return res;
    }
}

云服务器 GPU云服务器 subarray Maximum Product 阿里大鱼product

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

转载请注明本文地址：https://www.ucloud.cn/yun/65661.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
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] Sliding Window Maximum/Median

摘要：窗口前进，删队首元素保证队列降序加入当前元素下标从开始，每一次循环都将队首元素加入结果数组 Sliding Window Maximum Problem Given an array of n integer with duplicate number, and a moving window(size k), move the window at each iteration fro...

crelaber 2019-08-14 14:33 评论0 收藏0
[LintCode/LeetCode] Range Addition

Problem Assume you have an array of length n initialized with all 0s and are given k update operations. Each operation is represented as a triplet: [startIndex, endIndex, inc] which increments each el...

endless_road 2019-08-16 12:46 评论0 收藏0