乘积最大子数组

2020-12-06

152. 乘积最大子数组

难度中等953

给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

示例 1:

1
2
3

输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

示例 2:

1
2
3

输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

动态规划（第二次）

分情况讨论：

如果当前的值是正的，要与最大值做乘法才能得到最大值
如果当前的值是负的，要与最小值做乘法才能得到最大值

public class Solution {
    public double maxProduct(double[] arr) {
        int n = arr.length;
        if(n==0)return 0;
        double []dpMax = new double[n];
        double []dpMin = new double[n];
        double max = arr[0];
        dpMax[0] = arr[0];
        dpMin[0] = arr[0];
        for(int i=1;i<n;i++){
            if(arr[i]>0){
                dpMax[i]= Math.max(arr[i],dpMax[i-1]*arr[i]);
                dpMin[i]= Math.min(arr[i],dpMin[i-1]*arr[i]);
            }else{
                dpMax[i]= Math.max(arr[i],dpMin[i-1]*arr[i]);
                dpMin[i]= Math.min(arr[i],dpMax[i-1]*arr[i]);
            }
            max = Math.max(dpMax[i],max);
        }
        return max;
    }
}

动态规划分情况讨论

因为数字中有正数和负数，正数乘以最大值结果最大，负数乘以最小值结果最大，所以要维护两个表格，一个用来存放当前的最大值一个用来存放当前的最小值。

最后从最大值表中选择最大的一个值即为结果，因为在相乘的过程中子数组要是连续的才可以，中间有正负相间时，不是连续的，所以最大值不是连续的，要从中选择最大的那个值。

class Solution {
    public int maxProduct(int[] nums) {
        int[] max = new int[nums.length];
        int[] min = new int[nums.length];
        max[0] = nums[0];
        min[0] = nums[0];

        for (int i = 1; i < nums.length; i++) {
            if (nums[i] >= 0) {
                max[i] = Math.max(nums[i], max[i - 1] * nums[i]);
                min[i] = Math.min(nums[i], min[i - 1] * nums[i]);
            } else {
                max[i] = Math.max(nums[i], min[i - 1] * nums[i]);
                min[i] = Math.min(nums[i], max[i - 1] * nums[i]);
            }

        }

        int maxVal = Integer.MIN_VALUE;
        for (int i = 0; i < max.length; i++) {
            maxVal = Math.max(maxVal, max[i]);
        }

        return maxVal;
    }
}

官方动态规划

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;
    }
}

时间复杂度O(n),空间复杂度O(n)

优化空间

由于第 i 个状态只和第 i−1 个状态相关，根据「滚动数组」思想，我们可以只用两个变量来维护 i−1 时刻的状态，一个维护 fmax，一个维护fmin


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;
    }
}

时间复杂度O（n），空间复杂度O(1)

参考文献

作者：LeetCode-Solution

链接：https://leetcode-cn.com/problems/maximum-product-subarray/solution/cheng-ji-zui-da-zi-shu-zu-by-leetcode-solution/

来源：力扣（LeetCode）

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。