百度：最大子数组乘积

题目描述

给定一个double类型的数组arr，其中的元素可正可负可0，返回子数组累乘的最大乘积。例如arr=[-2.5，4，0，3，0.5，8，-1]，子数组[3，0.5，8]累乘可以获得最大的乘积12，所以返回12。

解：

子数组问题一般就直接DP做就很快，那么这里最普通的DP做法应该就是二维表，这道题显然不需要全遍历，因为 a[i[[j] 和 a[j][i] 是一样的，所以我们需要O(n^2/2)的遍历，即三角遍历，而非正方形遍历。那么辅助空间上，这道题是逐行求解，其实辅助空间可以压缩到O(1)级别，根本就不需要建二维表。

看一下子结构：从 arr[i] 到 arr[j] 的乘积：a[i][j] = a[i][j-1] * arr[j]；//arr[]是原始数组，a[]是DP数组

public class Solution { public double maxProduct(double[] arr) { //arr.length==0无解，根本就没法返回一个正解 -> double不能是null //这里默认arr.length>0，arr[0]存在 double max=arr[0],sum; for(int i=0;i<arr.length;i++){ sum=arr[i]; if(sum>max) max=sum; for(int j=i+1;j<arr.length;j++){ sum=sum*arr[j]; if(sum>max) max=sum; } } return max; } }