1.简述: 描述 输入一个长度为 n 的整型数组 nums,数组中的一个或连续多个整数组成一个子数组。求所有子数组的乘积的最大值。 1.子数组是连续的,且最小长度为 1 ,最大长度为 n
1.简述:
描述输入一个长度为 n 的整型数组 nums,数组中的一个或连续多个整数组成一个子数组。求所有子数组的乘积的最大值。
1.子数组是连续的,且最小长度为 1 ,最大长度为 n
2.长度为 1 的子数组,乘积视为其本身,比如 [4] 的乘积为 4
3.该题的数据保证最大的乘积不会超过 int 的范围,即不超过
数据范围:
输入描述:
第一行输入一个正整数 n ,表示数组的长度
第二行输入 n 个整数,表示数组中的值。
输出描述:输出子数组的乘积的最大值
示例1输入:
43 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
输出:
122.代码实现:
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);
}
}