LeetCode_动态规划_中等_152.乘积最大子数组

左手的ㄟ右手 2023-10-06 22:43 19阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

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

测试用例的答案是一个 32 位整数。

**子数组是数组的连续子序列。**

**示例 1：**  
输入: nums = \[2,3,-2,4\]  
输出: 6  
解释: 子数组 \[2,3\] 有最大乘积 6。

**示例 2：**  
输入: nums = \[-2,0,-1\]  
输出: 0  
解释: 结果不能为 2, 因为 \[-2,-1\] 不是子数组。

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

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/maximum-product-subarray

## 2.思路 ##

（1）暴力穷举法  
使用两层 for 循环来穷举所有的子数组，并且使用 res 来保存最大子数组所对应的乘积即可。

（2）动态规划  
思路参考[本题官方题解][Link 1]。

## 3.代码实现（Java） ##

//思路1————暴力穷举法
    class Solution {
        
        public int maxProduct(int[] nums) {
        
            // res 保存乘积最大子数组所对应的乘积，初始值为 Integer.MIN_VALUE
            int res = Integer.MIN_VALUE;
            int length = nums.length;
            //循环穷举所有的子数组，并用 res 保存乘积最大子数组所对应的乘积
            for (int i = 0; i < length; i++) {
        
                int tmp = nums[i];
                res = Math.max(res, nums[i]);
                for (int j = i + 1; j < length; j++) {
                       
                    tmp *= nums[j];
                    res = Math.max(res, tmp);
                }
            }
            return res;
        }
    }

//思路2————动态规划
    class Solution {
        
        public int maxProduct(int[] nums) {
        
            int length = nums.length;
            /*           
                maxF[i]: 以第 i 个元素结尾的乘积最大子数组的乘积
                minF[i]: 以第 i 个元素结尾的乘积最小子数组的乘积
                维护最大连续正积 MaxF 和最大连续负积 MinF，根据 nums[i] 的值对其进行更新
            */
            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]));
            }
            return Arrays.stream(maxF).max().getAsInt();
        }
    }

> 与 System.arraycopy 方法有关的知识可以参考[Java 基础——System.arraycopy() 与 Arrays.copyOf() 的联系与区别][Java _System.arraycopy_ _ Arrays.copyOf_]这篇文章。

[Link 1]: https://leetcode.cn/problems/maximum-product-subarray/solution/cheng-ji-zui-da-zi-shu-zu-by-leetcode-solution/
[Java _System.arraycopy_ _ Arrays.copyOf_]: https://xgqngu.blog.csdn.net/article/details/129899439