[数据结构与算法]LeetCode刷题——152. 乘积最大子数组

面试刷题第五天

LeetCode刷题——152. 乘积最大子数组

1、题目描述

给你一个整数数组 nums，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。测试用例的答案是一个 32-位整数。子数组是数组的连续子序列。

提示:
（1）1 <= nums.length <= 2 * 104。
（2）-10 <= nums[i] <= 10。
（3）nums 的任何前缀或后缀的乘积都保证是一个32-位整数。

2、解题思路(一）：动态规划

采用动态规划的思想完成，分三种情况：
（1）第一，可能是只有最后一个，例如：数组[0，0， 2]。
（2）第二，可能是最后一个乘前面的最大值，例如：数组[4，1,，2， 3]。
（3）第三，可能是最后一个乘前面的最小值，例如：数组[4，1，-2，-3]。
Java代码如下：

class Solution {
    public int maxProduct(int[] nums) {
        int ans = nums[0];
        //上一步的最小
        int premin = nums[0];
        //上一步的最大
        int premax = nums[0];
        for(int i=1; i<nums.length; i++){
            int p1 = nums[i];
            int p2 = nums[i] * premax;
            int p3 = nums[i] * premin; 
            int curMin = Math.min(p1, Math.min(p2, p3));
            int curMax = Math.max(p1, Math.max(p2, p3));
            //替换上一步的最大和最小
            premin = curMin;
            premax = curMax;
            ans = Math.max(ans, premax);
        }
        return ans;
    }
}

3、算法分析

记nums元素个数为n。
（1）时间复杂度：程序一次循环遍历了nums，故时间复杂度为O(n)。
（2）空间复杂度：使用了常数个临时变量作为辅助空间，与n无关，故空间复杂度为O(1)。
（3）该算法，同样也适用于double类型的数组。

4、解题思路（二）

求最大值，可以看成求被0拆分的各个子数组的最大值。当一个数组中没有0存在，则分为两种情况：
（1）若负数为偶数个，则最大值为整个数组中所有的值相乘；
（2）若负数为奇数个，则从左边开始，乘到最后一个负数停止会生成一个“最大值”，从右边开始，乘到最后一个负数停止也会生成一个“最大值”，比较两者，得出最大值。
Java代码如下：

class Solution {
    public int maxProduct(int[] nums) {
        int a = 1;
        int max = nums[0];
        for(int num : nums){
            a = a * num;
            if(max < a){
                max = a;
            }
            if(num == 0){
                a = 1;
            }
        }
        a = 1;
        for(int i=nums.length - 1; i>=0; i--){
            a = a * nums[i];
            if(max < a){
                max = a;
            }
            if(nums[i] == 0){
                a = 1;
            }
        }
        return max;
    }
}