class Solution {
    // 两种方法： 方法一:用两个变量，记录以某个索引为末尾的子数组的最大乘积和最小乘积
    // 遍历
    // 方法二：dpMax[i], dpMin[i]维护两个动态规划数组，一个用来记录最大值，一个用来记录最小值

    public int maxProduct(int[] nums) {
    //    int min = nums[0];
    //    int max = nums[0]; // 当前索引位置的乘积最大值
    //    int res = nums[0]; // 当前所有位置的乘积最小值
    //    for (int i = 1; i < nums.length; i++) {
    //     if (nums[i] < 0) { // 如果nums[i] < 0 交换最大最小值
    //         int temp = max;
    //         max = min;
    //         min = temp;
    //     }
    //     max = Math.max(nums[i], nums[i]*max);
    //     min = Math.min(nums[i], nums[i]* min);
    //     res = Math.max(res,max);
    //    }
    //    return res;
        int n = nums.length;
        int[] dpMax = new int[n];
        int[] dpMin = new int[n];
        int res = nums[0];
        dpMax[0] = nums[0];dpMin[0] = nums[0];
        for (int i = 1; i < n; i++) {
            dpMax[i] = Math.max(nums[i],Math.max(nums[i]*dpMax[i-1],nums[i]*dpMin[i-1]));
            dpMin[i] = Math.min(nums[i], Math.min(nums[i] * dpMax[i-1],nums[i]*dpMin[i-1]));
            res = Math.max(res, dpMax[i]);
        }
        return res;
      

    }
}