题解 | #子数组最大乘积#

import java.lang.Math;
//动态规划
public class Solution {
    public double maxProduct(double[] arr) {
        int length = arr.length;
        //特殊值（空数组）处理
        if(length == 0){
            return 0;
        }
        //数组长度为1
        if(length == 1){
            return arr[0];
        }
        double[] max_dp = new double[length];//最大值数组,max_dp[i]表示前i个数中的最大乘积
        double[] min_dp = new double[length];//最小值数组
        max_dp[0] = arr[0];
        min_dp[0] = arr[0];
        double max = arr[0];
        for(int i=1;i<length;i++){
            //动态规划，最优子结构，状态转换方程。
            //使用两个dp数组是因为元素中的数可以为负数，有负号影响（负数*最小值也可能是最大值）。
            //最大值可以有三个来源：
            //一是数组当前的值（arr[i]）；
            //二是数组当前的值（arr[i]）*max_dp[i-1]，即是正数*最大值；
            //三是数组当前的值（arr[i]）*min_dp[i-1]，即是负数*最小值；
            //最大值来源不能是max_dp[i-1]的原因是题目要求的是子数组（连续）的最大乘积。
            max_dp[i] = Math.max(Math.max(min_dp[i-1]*arr[i],arr[i]),max_dp[i-1]*arr[i]);
            min_dp[i] = Math.min(Math.min(max_dp[i-1]*arr[i],arr[i]),min_dp[i-1]*arr[i]);
            if(max_dp[i] > max){
                max = max_dp[i];
            }
        }
        
        return max;
    }
}