leetcode152 Maximum Product Subarray

Arno 發布于2019-08-16 10:57 / 1964人閱讀

摘要：題目要求從一個整數數組中找到一個子數組，該子數組中的所有元素的乘積最大。比如數組的最大乘積子數組為思路與代碼這題目考察了動態編程的思想。至于為什么還要比較，是因為如果是一個負數的，那么之前的最小乘積在這里可能就成為了最大的乘積了。

題目要求

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

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

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