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

1.简述:

描述

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

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

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

3.该题的数据保证最大的乘积不会超过 int 的范围,即不超过#yyds干货盘点# 动态规划专题:连续子数组的最大乘积

数据范围:

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

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

输入描述:

第一行输入一个正整数 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
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);
}
}
发表评论

相关文章