資訊專欄INFORMATION COLUMN
摘要：題目要求從一個(gè)整數(shù)數(shù)組中找到一個(gè)子數(shù)組，該子數(shù)組中的所有元素的乘積最大。比如數(shù)組的最大乘積子數(shù)組為思路與代碼這題目考察了動(dòng)態(tài)編程的思想。至于為什么還要比較，是因?yàn)槿绻且粋€(gè)負(fù)數(shù)的，那么之前的最小乘積在這里可能就成為了最大的乘積了。
題目要求
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.
從一個(gè)整數(shù)數(shù)組中找到一個(gè)子數(shù)組，該子數(shù)組中的所有元素的乘積最大。
比如數(shù)組[2,-3,-2,4]的最大乘積子數(shù)組為[2,3]
這題目考察了動(dòng)態(tài)編程的思想。從一個(gè)更高的視角看這個(gè)問題，我們可以推理一下，假如我們知道了以第i位為結(jié)尾的子數(shù)組的最大乘積值和最小乘積值，我們能否知道第(i+1)位的最大乘積值和最小乘積值呢？答案是肯定的。因?yàn)橹恍枰容^max( nums[i+1], maxProduct[i]*nums[i+1], minProduct[i]*nums[i+1])就可以了。
至于為什么還要比較minProduct[i]*nums[i+1]，是因?yàn)槿绻鹡ums[i+1]是一個(gè)負(fù)數(shù)的，那么之前的最小乘積在這里可能就成為了最大的乘積了。
代碼如下：
public int maxProduct(int[] nums) {
//記錄在遍歷過程中所得到的最大乘積值
int max = nums[0];
for(int i = 1, curMax = max, curMin = max ; i
想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號(hào)！將會(huì)不定期的發(fā)放福利哦~
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/70775.html
摘要：復(fù)雜度思路要保留一個(gè)到某一位來看的最大值和最小值。因?yàn)樵跀?shù)組中有負(fù)數(shù)的出現(xiàn)，所以到這一位為止的能得到的最大值，可能是由之前的最大值和這個(gè)數(shù)相乘得到，也可能是最小值和這個(gè)數(shù)相乘得到的。 Leetcode[152] Maximum Product Subarray Find the contiguous subarray within an array (containing at le...
摘要：問題本質(zhì)本質(zhì)動(dòng)態(tài)規(guī)劃問題。局部最優(yōu)，全局最優(yōu)。乘法問題，存在的情況是負(fù)數(shù)或者正數(shù)，或者從當(dāng)前數(shù)開始新的連續(xù)元素相乘可能發(fā)生的情況在某個(gè)節(jié)點(diǎn)，繼續(xù)之前的增大減小，從此節(jié)點(diǎn)轉(zhuǎn)折。所以只要在局部動(dòng)態(tài)中，保持最大最小當(dāng)前，進(jìn)行判斷保留即可。 Given an integer array nums, find the contiguous subarray within an array (co...
摘要：這是一道簡單的動(dòng)規(guī)題目，同步更新數(shù)組解決了為負(fù)數(shù)的問題。即使是求最小乘積子序列，也可以通過取和的最小值獲得。 Problem Find the contiguous subarray within an array (containing at least one number) which has the largest product. Example For example, g...
摘要：前言從開始寫相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時(shí)也沒有按順序?qū)懍F(xiàn)在翻起來覺得蠻亂的?？赡艽蠹铱粗卜浅２环奖?。所以在這里做個(gè)索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新 前言 從開始寫leetcode相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時(shí)也沒有按順序?qū)憽F(xiàn)在翻起來覺得蠻亂的?？赡艽蠹铱粗卜浅２环奖?。所以在這里做個(gè)索引嘻嘻。 順序整理 1~50 1...
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 ...
閱讀 2494·2021-11-22 15:35
閱讀 3792·2021-11-04 16:14
閱讀 2722·2021-10-20 13:47
閱讀 2524·2021-10-13 09:49
閱讀 2095·2019-08-30 14:09
閱讀 2425·2019-08-26 13:49
閱讀 913·2019-08-26 10:45
閱讀 2799·2019-08-23 17:54
