題目描述
題目
解題思路
- 動態(tài)規(guī)劃陈惰，從0-i的子數(shù)組的最大乘積為max,最小乘積為min，則0-i+1的最大乘積為
i+1為正數(shù)：max(max*(i+1),(i+1))
i+1為負數(shù)：max(min*(i+1),(i+1))
class Solution {
public int maxProduct(int[] nums) {
if(nums == null || nums.length == 0)
return 0;
int max = nums[0];
int min = nums[0];
int result = nums[0];
for(int i = 1 ; i < nums.length;i++){
if(nums[i]>0){
int temp = max;
max = Math.max(max*nums[i],nums[i]);
min = Math.min(min*nums[i],nums[i]);
}else{
int temp = max;
max = Math.max(min*nums[i],nums[i]);
min = Math.min(temp*nums[i],nums[i]);
}
if(max > result)
result = max;
}
return result;
}
}
