数组中子数组的最大累乘积

用动态规划求解，思路跟求数组最大连续累乘值相同。在遍历数组的过程中，比较当前数是累乘在之前的结果上能更大，还是从当前的数重新开始乘会更大。但在遇到负数时，要将之前累乘策略中的最大和最小值交换，因为符号反转能使得数值大小两极反转。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] strArr = br.readLine().split(" ");
        double[] nums = new double[n];
        for(int i = 0; i < n; i++) nums[i] = Double.parseDouble(strArr[i]);
        double dmax = 1.0, dmin = 1.0;
        double max = Double.MIN_VALUE;
        for(int i = 0; i < n; i++){
            if(nums[i] < 0){
                // 遇到负数时，需要交换一下到目前为止的最大累乘值和最小累乘值，因为会使得最大的变最小，最小的变最大
                double temp = dmax;
                dmax = dmin;
                dmin = temp;
            }
            dmax = Math.max(dmax * nums[i], nums[i]);
            dmin = Math.min(dmin * nums[i], nums[i]);
            max = Math.max(max, dmax);
        }
        System.out.println(String.format("%.2f", max));
    }
}

首先，这题比较坑的地方就是最后要输出两位小数，可以用String.format("%.2f",res)来保留两位小数，否则默认一位。

思路就是从左到右扫描，假设i位置是子数组的最后一个数，看以这个数结尾最大的乘积是多少，是一个一维的动态规划，当然，压缩一下空间，用两个变量就可以遍历了。

因为有负数，所以还要保留一下每一次循环最小的值，也许下一次遇上一个负数之后，负负得正，变成了最大值了

//本题可以直接上动态规划，假设i位置是一个子数组的最后一位，它的最大乘积是多少,
//由于包含负数，所以最小的也要查看一下,并在每一次循环，看看这个负数有没有晋升（变成最大正数）的机会

import java.util.*;


public class Main {
    public static void main(String args[])
    {
        Scanner cin = new Scanner(System.in);
        int n;
        while(cin.hasNext())
        {
            n = cin.nextInt();
            double[] a=new double[n];

            for(int i=0;i<n;i++){
                a[i]=cin.nextDouble();
            }
            process_getMaxMulti(a);

        }

    }

    public static void process_getMaxMulti(double[] a){

        double max=a[0];
        double min=a[0];
        double res=max;

        for(int i=1;i<a.length;i++){
            //源代码的错误是，用改了之后的max值来更新min
            double maxEnd=max*a[i];
            double minEnd=min*a[i];

            max=Math.max(Math.max(maxEnd,a[i]),minEnd);

            min=Math.min(Math.min(minEnd,a[i]),maxEnd);


            res=Math.max(res,max);
        }
        System.out.println(String.format("%.2f", res));

    }

}