力扣AC：乘积最大子数组 - 动态规划

题目链接

乘积最大子数组

题目描述

实现代码

思路：记dp[i]表示前i个元素的子数组的最大乘积，如果按照以下的状态转移方程：

dp[i] = max(dp[i-1] * nums[i], nums[i])；

最终的结果将是错误的，只有在所有元素都大于0的情况下才正确，但是所有元素大于0，其最大子数组乘积就是所有元素相乘，所以这个状态转移方程没有意义；

首先思考为何是错误的，因为如果数组里面的元素包含了负数，那么对于第一个负数而言，会导致数组和变小，就不会进行计算，而如果再遇到一个负数，我们期望的是两个负数再次进行相乘判断，而使用这个状态转移方程最终会导致所有的负数都会被忽略，同时0也是一样的，我们期望从0的两边进行判断，而最终的该方程就会导致不会进行分段判断了；

如果当前第i个元素的值为负数，那么我们就应该选择前i-1个元素的子数组中的最大正数乘积；
如果当前第i个元素的值为整数，那么我们就应该选择前i-1个元素的子数组中的最小负数乘积；
而对于当前第i个元素为0的情况可以不做特殊考虑，因为我们最终计算的是每个位置所对应的最大乘积，然后在进行一遍遍历找到最大的即可；实现代码如下：

class Solution {
    public int maxProduct(int[] nums) {
        int length = nums.length;
        int[] maxF = new int[length];
        int[] minF = new int[length];
        System.arraycopy(nums, 0, maxF, 0, length);
        System.arraycopy(nums, 0, minF, 0, length);
        for (int i = 1; i < length; ++i) {
            maxF[i] = Math.max(maxF[i - 1] * nums[i], Math.max(nums[i], minF[i - 1] * nums[i]));
            minF[i] = Math.min(minF[i - 1] * nums[i], Math.min(nums[i], maxF[i - 1] * nums[i]));
        }
        int ans = maxF[0];
        for (int i = 1; i < length; ++i) {
            ans = Math.max(ans, maxF[i]);
        }
        return ans;
    }
}

考虑一下优化，因为对于第i个元素子数组的最大乘积，其结果只与第i-1个元组子数组的最大正数乘积或者最小负数乘积有关，因此可以直接使用变量进行存储即可，优化代码如下：

class Solution {
    public int maxProduct(int[] nums) {
        int maxF = nums[0], minF = nums[0], ans = nums[0];
        int length = nums.length;
        for (int i = 1; i < 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(maxF, ans);
        }
        return ans;
    }
}