前言

当前所有算法都使用测试用例运行过，但是不保证100%的测试用例，如果存在问题务必联系批评指正~

在此感谢左大神让我对算法有了新的感悟认识！

问题介绍

原问题
给定一个数组arr，求arr总累乘最大的子数组累乘积
如：
arr = {0.1,0.1，100}
结果为100

解决方案

原问题：
动态规划思想，求以每一个数为底的子数组最大累乘积
1、对于每一个arr[i](i>0),以arr[i]为底的子数组必须乘以arr[i],但是arr[i]可能为负数，可能为正数也可能是0
2、当arr[i] 为0，则不管前面是什么，累乘积都是0
3、当arr[i] <0，则dp[i-1]存储的最大累乘积乘以 arr[i]后会变成以arr[i]结尾的最小累乘积，因此需要另一个dp存储最小累乘积，这样才能获取到以arr[i]结尾的最大累乘积
4、当arr[i] > 0, 则 dp[i-1]存储的最大累乘积乘以 arr[i]后会变成以arr[i]结尾的最大累乘积

由于只有dp[i]和dp[i-1]的关系，所以可以将dp数组的空间复杂度降低到O(1)

代码编写

java语言版本

原问题：
方法一:

    /*** 二轮测试：获取最大的累乘数组* @param arr* @return*/public static double getMaxMulti(double[] arr) {if (arr == null || arr.length == 0) {throw new RuntimeException("invalid arr");}double max = arr[0];double min = arr[0];double res = arr[0];for (int i = 1; i < arr.length; i ++) {double curMax = arr[i] * max;double curMin = arr[i] * min;max = Math.max(arr[i], Math.max(curMax, curMin));min = Math.min(arr[i], Math.min(curMax, curMin));res = Math.max(res, max);}return res;}public static void main(String[] args) {System.out.println(getMaxMulti(new double[]{0.1, 0.1, 100}));}

c语言版本

正在学习中

c++语言版本

正在学习中

思考感悟

1、首先这道题介绍的思想就是递归思想，但是需要理解dp[i]的计算
2、对于动态规划如果只存在dp[i]和dp[i-1]的关系，或者即使是dp[i]和dp[i-2],dp[i-3]…这种显式定义的状态转换关系，都可以降低维度，但是如果dp[i]需要计算出前面状态中满足某个条件的状态时，比如找出前面状态中最小的那个dp[i-j]，那么空间复杂度就不能降低了。