本文共 1646 字，大约阅读时间需要 5 分钟。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/maximum-product-subarray

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

示例 1:

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

示例 2:

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

前言：

做这道题，很恼火，自己的想法才一半，就短路了，还需再努力，果真还是解题里边的大佬牛逼！

思路：

这其实说白了就是子串的题目，所以必须使用动态规划去做。做 dp 的题目，我觉得首先最重要的不是状态转移方程，而是 dp 数组的含义是什么，只有这个确定对了，状态方程才能很好的列出来！！！

这里的 dp 数组指的是以第 i 个数 结尾的 连续子序列，由于存在负数，所以必须维护两个 dp 数组，其实这里根本用不到数组，但是为了更加清晰的看到 dp 的思想，我还是用数组来表达吧。

我们先考虑都是正数的情况。dp_max[i] 的含义我们已经讲过了，dp_max[i] = Math.max(nums[i-1],dp_max[i-1]*nums[i-1])，即 dp_max[i] 这个值只会在这两者产生，要么 乘上之前的会更大，要么 舍弃前面的。

接下来考虑负数的情况，所以我们有必要维护一个 dp_min，思路是一模一样的，当遍历的元素为负数时，我们只需要把 dp_max[i-1]，dp_min[i-1]交换即可。 最后，只要找到所有dp_max中的数值最大的那个，就是我们需要的值了。

代码：

class Solution {
       public int maxProduct(int[] nums) {
           if(nums == null || nums.length == 0){
               return 0;        }        int len = nums.length;        // dp_max[i] 指的是以第 i 个数结尾的 乘积最大 的连续子序列        // dp_min[i] 指的是以第 i 个数结尾的 乘积最小 的连续子序列        int[] dp_Max = new int[len+1];        int[] dp_Min = new int[len+1];        dp_Max[0] = 1;        dp_Min[0] = 1;         int res = Integer.MIN_VALUE;                for(int i=1; i<=len; i++){
               // 如果数组的数是负数，那么会导致 max 变成 min，min 变成 max            // 故需要交换dp             if(nums[i-1] < 0){
                   int temp = dp_Min[i-1];                dp_Min[i-1] = dp_Max[i-1];                dp_Max[i-1] = temp;            }            dp_Max[i] = Math.max(nums[i-1]*dp_Max[i-1], nums[i-1]);            dp_Min[i] = Math.min(nums[i-1]*dp_Min[i-1], nums[i-1]);            res = Math.max(res, dp_Max[i]);        }        return res;    }}

转载地址：http://mswpi.baihongyu.com/