#yyds干货盘点# 动态规划专题：连续子数组的最大乘积

1.简述：

描述

输入一个长度为 n 的整型数组 nums，数组中的一个或连续多个整数组成一个子数组。求所有子数组的乘积的最大值。

1.子数组是连续的，且最小长度为 1 ，最大长度为 n

2.长度为 1 的子数组，乘积视为其本身，比如 [4] 的乘积为 4

3.该题的数据保证最大的乘积不会超过 int 的范围，即不超过

数据范围:

输入描述：

第一行输入一个正整数 n ，表示数组的长度

第二行输入 n 个整数，表示数组中的值。

输出描述：

输出子数组的乘积的最大值

示例1

输入：

4
3 2 -2 4

输出：

6

说明：

子数组[3,2]的乘积为6，[3,2,-1,4]的乘积为-24，[4]的乘积为4，故返回6

示例2

输入：

3
-3 0 -2

输出：

0

说明：

因为0在中间，所有包含0的子数组的乘积都为0，另外的数都是负数，所以最大乘积的子数组为[0]，返回为0，因为子数组要求是连续的，所以[-3,-2]不是[-3,0,-2]的子数组，所以不能为6，

示例3

输入：

3
-3 2 -2

输出：

12

2.代码实现：

import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }
        int[] dpMax = new int[n];
        int[] dpMin = new int[n];
        dpMax[0] = nums[0];
        dpMin[0] = nums[0];
        for (int i = 1; i < n; i++) {
            dpMax[i] = Math.max(dpMax[i - 1] * nums[i], Math.max(dpMin[i - 1] * nums[i], nums[i]));
            dpMin[i] = Math.min(dpMax[i - 1] * nums[i], Math.min(dpMin[i - 1] * nums[i], nums[i]));
        }
        int res = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            if (dpMax[i] > res) res = dpMax[i];
        }
        System.out.println(res);
    }
}