[LintCode/LeetCode] Maximum Product Subarray

meteor199 發布于2019-08-14 15:21 / 1336人閱讀

摘要：這是一道簡單的動規題目，同步更新數組解決了為負數的問題。即使是求最小乘積子序列，也可以通過取和的最小值獲得。

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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