【题目】
给定一个 double 类型的数组 arr, 其中的元素可正、可负、可 0，返回子数组累乘的最大乘积。例如, arr = [-2.5, 4, 0, 3, 0.5, 8, -1], 子数组 [3, 0.5, 8] 累乘可以获得最大的乘积 12，所以返回 12.
【要求】
如果 arr 的长度为 N，要求时间复杂度为 O(N), 额外空间复杂度为 O(1).
【难度】
两星
【解答】
所有的子数组都会以某一个位置结束，所以，如果求出以每一个位置结尾的子数组最大的累乘积，在所有的累乘积中最大的那个累乘积就是最终的结果。即结果=Max{以 arr[0] 结尾的累乘积, .... , 以 arr[arr.length-1] 结尾的累乘积}。
如何求出所有以 i 位置(arr[i])结尾的累乘积呢？假设以 arr[i-1] 结尾的最小累乘积为 min, 以 arr[i-1] 结尾的最大累乘积为 max。那么，以 arr[i] 结尾的最大累乘积只有以下三种可能：
- 可能是 max*arr[i]。例如，[3,4,5] 的最大累乘积是在算到 5 的时候，为 60。
- 可能是 min*arr[i]。例如，[-2,3,-4] 的最大累乘积是在算到 -4 的时候，为 24。
- 可能是 arr[i]。例如，[0.1,0.1,100] 的最大累乘积是在算到 100 的时候，为 100。
这三种可能的值中最大的那个就作为以 i 位置结尾的最大累乘积，最小的作为最小累乘积，然后继续计算以 i+1 位置结尾的时候，如此重复，直到计算结束。
具体实现过程请参考如下代码中 maxProduct 方法。
1 public class Main { 2 3 public static void main(String[] args) { 4 double[] arr = {-2.5, 4, 0, 3, 0.5, 8, -1}; 5 System.out.println(new Main().maxProduct(arr));//12.0 6 } 7 8 public double maxProduct(double[] arr) { 9 if(arr == null || arr.length == 0) return 0;10 11 double max = arr[0]; // max 表示以 arr[i-1]位置结尾的子数组的最大累乘积12 double min = arr[0]; // min 表示以 arr[i-1]位置结尾的子数组的最小累乘积13 double res = arr[0]; // 最大的累乘积14 double maxEnd = 0; //表示最大累乘积的一种可能：以 arr[i-1]位置结尾的子数组的最大累乘积*arr[i]15 double minEnd = 0; //表示最大累乘积的一种可能：以 arr[i-1]位置结尾的子数组的最小累乘积*arr[i]16 17 for(int i = 1, len = arr.length; i < len; i++){18 maxEnd = max * arr[i];19 minEnd = min * arr[i];20 max = Math.max(Math.max(maxEnd, minEnd), arr[i]);21 min = Math.min(Math.min(maxEnd, minEnd), arr[i]);22 res = Math.max(max, res);23 }24 25 return res;26 }27 28 }