【leetcode hot 100 152】乘积最大子数组

错误解法：db[i]表示以i结尾的最大的非空连续，动态规划：dp[i] = Math.max(nums[i], nums[i] * dp[i - 1]);

class Solution {
    public int maxProduct(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n]; // db[i]表示以i结尾的最大的非空连续
        dp[0] = nums[0];
        for (int i = 1; i < n; i++) {
            dp[i] = Math.max(nums[i], nums[i] * dp[i - 1]);
            // 不需要循环，直接用dp[i-1]判断即可
            // int curr_max = nums[i];
            // dp[i] = nums[i];   // 赋初始值
            // for(int j = i-1; j>=0; j--) {
            //     curr_max = curr_max * nums[j];
            //     dp[i] = Math.max(dp[i], curr_max);
            // }
        }
        return Arrays.stream(dp).max().getAsInt();
    }
}

错误原因：未考虑负数情况

解法一：（动态规划）①定义：dp[i]表示以下标为i的连续子数组最大乘积，dp[n]；dp_helperi表示以下标为i的连续子数组最小乘积 ②初始状态：dp[0]=nums[0] dp_helper[0]=0 ③状态转移方程：dp[i] = Math.max(dp[i-1],dp[i-1]*nums[i],dp_helper[i-1]*nums[i])；dp_helper[i] = Math.min(dp_helper[i-1],dp[i-1]*nums[i],dp_helper[i-1]*nums[i])

考虑当前位置如果是一个负数的话，那么我们希望以它前一个位置结尾的某个段的积也是个负数，这样就可以负负得正，并且我们希望这个积尽可能「负得更多」，即尽可能小。如果当前位置是一个正数的话，我们更希望以它前一个位置结尾的某个段的积也是个正数，并且希望它尽可能地大。于是这里我们可以再维护一个$f_{min}(i)$，它表示以第$i$个元素结尾的乘积最小子数组的乘积，那么我们可以得到这样的动态规划转移方程：

import java.util.*;

/**
 * @author longyy
 * @version 1.0
 */
class Solution79 {
    public int maxProduct(int[] nums) {
        // 定义：dp[i]表示以下标为i的连续子数组最大乘积，dp[n]；dp_helper[i]表示以下标为i的连续子数组最小乘积
        // dp_helper[i](应对两个负数乘积更大的情况)
        // 初始状态：dp[0]=nums[0] dp_helper[0]=0
        // 状态转移方程：dp[i] = Math.max(dp[i-1],dp[i-1]*nums[i],dp_helper[i-1]*nums[i])
        //             dp_helper[i] = Math.min(dp_helper[i-1],dp[i-1]*nums[i],dp_helper[i-1]*nums[i])
        int n = nums.length;
        int[] dp = new int[n]; // db[i]表示以i结尾的最大的非空连续
        int[] dp_helper = new int[n]; // db[i]表示以i结尾的最小的非空连续
        dp[0] = nums[0];
        for (int i = 1; i < n; i++) {
            dp[i] = Math.max(Math.max(nums[i], nums[i] * dp[i - 1]), nums[i]*dp_helper[i-1]);
            dp_helper[i] = Math.min(Math.min(nums[i], nums[i]*dp_helper[i-1]), nums[i]*dp[i-1]);
        }
        return Arrays.stream(dp).max().getAsInt();
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] nums = new int[n];
        for(int nums_i=0; nums_i < n; nums_i++){
            nums[nums_i] = in.nextInt();
        }
        Solution79 solution79 = new Solution79();
        System.out.println(solution79.maxProduct(nums));
    }
}