题目描述

解题思路

本题主要难就难在有负数，所以求得时候不能只考虑最大的，如果为负数我们就要将本身来乘前面最小的，如果为正数，就需要乘前面最大的。
所以分两个状态来求。

写法一：

public int maxProduct(int[] nums) {
    int[] maxDp = new int[nums.length];
    int[] minDp = new int[nums.length];
    maxDp[0] = nums[0];
    minDp[0] = nums[0];
    int max = nums[0];
    for (int i = 1; i < nums.length; i++) {
        maxDp[i] = Math.max(maxDp[i - 1] * nums[i], Math.max(nums[i], minDp[i - 1] * nums[i]));
        minDp[i] = Math.min(minDp[i - 1] * nums[i], Math.min(nums[i], maxDp[i - 1] * nums[i]));
        max = Math.max(max, maxDp[i]);
    }
    return max;
}

写法二：

public int maxProduct(int[] nums) {
    int[][] dp = new int[nums.length][2];
    dp[0][0] = nums[0];
    dp[0][1] = nums[0];
    int max = nums[0];
    for (int i = 1; i < nums.length; i++) {
        dp[i][0] = Math.max(dp[i - 1][0] * nums[i], Math.max(nums[i], dp[i - 1][1] * nums[i]));
        dp[i][1] = Math.min(dp[i - 1][1] * nums[i], Math.min(nums[i], dp[i - 1][0] * nums[i]));
        max = Math.max(max, dp[i][0]);
    }
    return max;
}

滚动数组优化：

// 滚动数组优化
public int maxProduct(int[] nums) {
    int minF = nums[0], maxF = nums[0], ans = nums[0];
    for (int i = 1; i < nums.length; i++) {
        int mx = maxF, mn = minF;
        maxF = Math.max(mx * nums[i], Math.max(nums[i], mn * nums[i]));
        minF = Math.min(mn * nums[i], Math.min(nums[i], mx * nums[i]));
        ans = Math.max(ans, maxF);
    }
    return ans;
}