資訊專欄INFORMATION COLUMN
摘要：這是一道簡(jiǎn)單的動(dòng)規(guī)題目，同步更新數(shù)組解決了為負(fù)數(shù)的問題。即使是求最小乘積子序列，也可以通過取和的最小值獲得。
Problem
Find the contiguous subarray within an array (containing at least one number) which has the largest product.
ExampleFor example, given the array [2,3,-2,4], the contiguous subarray [2,3] has the largest product = 6.
Note這是一道簡(jiǎn)單的動(dòng)規(guī)題目，同步更新min[]數(shù)組解決了nums[i]為負(fù)數(shù)的問題。即使是求最小乘積子序列，也可以通過取res和min[i]的最小值獲得。
Solutionpublic 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;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/65661.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...
摘要：?jiǎn)栴}本質(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...
摘要：題目要求從一個(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 num...
摘要：窗口前進(jìn)，刪隊(duì)首元素保證隊(duì)列降序加入當(dāng)前元素下標(biāo)從開始，每一次循環(huán)都將隊(duì)首元素加入結(jié)果數(shù)組 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...
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...
閱讀 2693·2023-04-25 15:15
閱讀 1330·2021-11-25 09:43
閱讀 1617·2021-11-23 09:51
閱讀 1095·2021-11-12 10:36
閱讀 2896·2021-11-11 16:55
閱讀 969·2021-11-08 13:18
閱讀 742·2021-10-28 09:31
閱讀 2065·2019-08-30 15:47
