题解 | JAVA DP#子数组最大乘积# [P1-T2]

dp, 定义:
min(i)为arr[0,i]包含arr[i]的最小子数乘积
max(i)为arr[0,i]包含arr[i]的最大子数乘积
注意min,max都是可正可负

很明显 min(i+1)只有三种可能：
 1. = min(i) * arr[i+1]  // 比如min(i) = -1, arr[i+1] = 2
 2. = max(i) * arr[i+1]  // 比如max(i) = 1, arr[i+1] = -2或者0.5
 2. = arr[i+1] // 比如min(i) = -1, max(i) = 0.5, arr[i+1] = -2
那么min(i+1) = Math.min(以上三种可能)
max(i+1)同理

然后每次loop跟新global的max (i.e. ans)就行

时间O(n)
空间O(1), 计算min/max(i+1)只需要存min/max(i), 还有个global max

代码：

public class Solution {
    public double maxProduct(double[] arr) {
      if (arr.length == 1) return arr[0];
      
      double min = 0.0, max = 0.0;
      double ans = Double.MIN_VALUE;

      for (double num : arr) {
        double a = min * num;
        double b = max * num;
        
        min = Math.min(num, Math.min(a, b));
        max = Math.max(num, Math.max(a, b));
        ans = Math.max(ans, max);
      }
      
      return ans;
    }
}