这种连续的还都挺简单的。因为涉及到负号，所有保存了两个状态。dp[i][0]表示以i为结尾的最大乘积，dp[i][1]表示以i为结尾的最小乘积。转换公式分下面两种情况：
if(nums[i] < 0){
dp[i][0] = Math.max(dp[i-1][1] * nums[i], nums[i]);
dp[i][1] = Math.min(dp[i-1][0] * nums[i], nums[i]);
}else{
dp[i][0] = Math.max(dp[i-1][0] * nums[i], nums[i]);
dp[i][1] = Math.min(dp[i-1][1] * nums[i], nums[i]);
}
边界条件为
dp[0][0] = nums[0];
dp[0][1] = nums[0];
整体代码如下：
public int maxProduct(int[] nums) {
if(nums.length == 0){
return 0;
}
int[][] dp = new int[nums.length][2];
dp[0][0] = nums[0];
dp[0][1] = nums[0];
//一个存最大 一个存最小
for(int i = 1 ; i < nums.length; i++){
if(nums[i] < 0){
dp[i][0] = Math.max(dp[i-1][1] * nums[i], nums[i]);
dp[i][1] = Math.min(dp[i-1][0] * nums[i], nums[i]);
}else{
dp[i][0] = Math.max(dp[i-1][0] * nums[i], nums[i]);
dp[i][1] = Math.min(dp[i-1][1] * nums[i], nums[i]);
}
}
int max = nums[0];
for(int i = 1 ; i < nums.length; i++){
max = Math.max(max, dp[i][0]);
}
return max;
}
image.png
