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

算法思想1：暴力法
解题思路：
对于求解子数组的最大乘积，只需要按照子数组的大小，进行遍历，最后记录最大乘积，输出结果即可

1、只包含一个元素，直接返回该元素；
2、包含两个或两个以上元素，暴力循环求乘积最大的连续子数组，返回乘积。
复杂度分析
时间复杂度：N表示数组的长度，两遍循环时间

空间复杂度：仅使用常数级空间变量
代码展示：

class Solution:
    def maxProduct(self , arr ):
        # write code here
        # 整数数组 nums 只包含一个元素
        if len(arr) == 1:
            return float(arr[0])
        # 记录整数数组 arr 中乘积最大的连续子数组的乘积
        maxres = arr[0]
        for i in range(len(arr)):
            # curmax 记录整数数组 arr 中当前乘积最大的连续子数组的乘积
            curmax = 1
            for j in range(i, len(arr)):
                curmax *= arr[j]
                # 不断更新 arr 中乘积最大的连续子数组的乘积 maxres
                maxres = max(maxres, curmax)
        return float(maxres)

解题思路2：动态规划
注意:题意是求数组中乘积最大的连续子数组
算法一时间复杂度较高，采用动态规划方法进行优化

算法流程：

1、遍历数组时计算当前最大值，不断更新
2、令imax为当前最大值，则当前最大值为
3、由于存在负数，那么会导致最大的变最小的，最小的变最大的。因此还需要维护当前最小值 ，
4、当负数出现时则imax与imin进行交换再进行下一步计算
图解：

复杂度分析
时间复杂度：N表示数组的长度，遍历一次数组时间

空间复杂度：仅使用常数级空间变量

public class Solution {
    public double maxProduct(double[] arr) {

        if (arr == null || arr.length == 0) {
            return 0;
        }

        double imin = 1;
        double imax = 1;
        double max = Integer.MIN_VALUE;

        // 遍历数组内元素
        for (int i = 0; i < arr.length; i++) {

            // 交换最大最小值
            if (arr[i] < 0) {
                double temp = imin;
                imin = imax;
                imax = temp;
            }

            // 更新最小 最大值，防止出现负数的情况
            imin = Math.min(arr[i], arr[i] * imin);
            imax = Math.max(arr[i], arr[i] * imax);

            // 寻找最大值
            max = Math.max(max, imax);
        }

        return max;
    }
}