题解 | #连续子数组的最大乘积#

import java.util.Arrays;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] a = new int[n];
        for(int i = 0; i < n; i++)a[i] = in.nextInt();
	 // 包含第i个数在内的连续子数组的乘积的最大值、最小值（用于维护负数乘以负数得到正数的情况）
        int[] dp_min = new int[n];
        int[] dp_max = new int[n];
        Arrays.fill(dp_min, Integer.MAX_VALUE);
        Arrays.fill(dp_max, Integer.MIN_VALUE);
        dp_min[0] = dp_max[0] = a[0];
        for(int i = 1; i < n; i++){
            dp_min[i] = Math.min(Math.min(dp_min[i-1]*a[i], dp_max[i-1]*a[i]), a[i]);
            dp_max[i] = Math.max(Math.max(dp_min[i-1]*a[i], dp_max[i-1]*a[i]), a[i]);
        }
        int max = Integer.MIN_VALUE;
        for(int i = 0; i < n; i++){
            max = Math.max(max, Math.max(dp_min[i], dp_max[i]));
        }
        System.out.println(max);
    }
}