本題考察的是動(dòng)態(tài)規(guī)劃
題目描述
給定一個(gè)整數(shù)數(shù)組 nums ，找出一個(gè)序列中乘積最大的連續(xù)子序列（該序列至少包含一個(gè)數(shù)）寿羞。
示例 1：
輸入: [2,3,-2,4]
輸出: 6
解釋: 子數(shù)組 [2,3] 有最大乘積 6
示例 2：
輸入: [-2,0,-1]
輸出: 0
解釋: 結(jié)果不能為 2, 因?yàn)?[-2,-1] 不是子數(shù)組。
題目思考
整數(shù)數(shù)組中有正數(shù)困介、負(fù)數(shù)和 0 顶滩。我們可以遍歷數(shù)組敛滋，求出到數(shù)組中每一個(gè)數(shù)字的連續(xù)乘積的最大值和最小值（之所以要保存最小值，是因?yàn)槿绻龅截?fù)數(shù)替废，越小的數(shù)與負(fù)數(shù)的乘積越大）箍铭。怎么求當(dāng)前數(shù)字連續(xù)乘積的最大值：如果當(dāng)前數(shù)字為正，則當(dāng)前數(shù)字連續(xù)乘積的最大值=Math.max(前一個(gè)數(shù)字連續(xù)乘積的最大值當(dāng)前數(shù)字椎镣，當(dāng)前數(shù)字)诈火；如果當(dāng)前數(shù)字為負(fù)，則當(dāng)前數(shù)字連續(xù)乘積的最大值=Math.max(前一個(gè)數(shù)字連續(xù)乘積的最小值當(dāng)前數(shù)字状答，當(dāng)前數(shù)字)冷守。
代碼
public int maxProduct(int[] nums) {
if(nums.length<1) return 0;
int[][] result = new int[nums.length][2];
result[0][0] = nums[0];
result[0][1] = nums[0];
int max = nums[0];
for(int i=1; i<nums.length; i++) {
if(nums[i]<0) {
result[i][0] = Math.max(result[i-1][1]*nums[i], nums[i]);
result[i][1] = Math.min(result[i-1][0]*nums[i], nums[i]);
} else {
result[i][0] = Math.max(result[i-1][0]*nums[i], nums[i]);
result[i][1] = Math.min(result[i-1][1]*nums[i], nums[i]);
}
max = Math.max(max, result[i][0]);
}
return max;
}
