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

算法思想一：暴力法

解题思路：

对于求解子数组的最大乘积，只需要按照子数组的大小，进行遍历，最后记录最大乘积，输出结果即可

1、只包含一个元素，直接返回该元素；
2、包含两个或两个以上元素，暴力循环求乘积最大的连续子数组，返回乘积。

代码展示：

Python版本

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)

复杂度分析

时间复杂度 $O(N^2)$ ：N表示数组的长度，两遍循环时间 $O(N^2)$

空间复杂度 $O(1)$ ：仅使用常数级空间变量

算法思想二：动态规划

解题思路：

算法一时间复杂度较高，采用动态规划方法进行优化

算法流程：

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

代码展示：

JAVA版本

import java.lang.Math;
public class Solution {
    public double maxProduct(double[] arr) {
        // 初始化
        double max = Integer.MIN_VALUE, imax = 1, imin = 1;
        // 遍历数组内元素
        for(int i=0; i<arr.length; i++){
            // 交换最大最小值
            if(arr[i] < 0){ 
              double tmp = imax;
              imax = imin;
              imin = tmp;
            }
            // 更新最小 最大值，防止出现负数的情况
            imax = Math.max(imax*arr[i], arr[i]);
            imin = Math.min(imin*arr[i], arr[i]);
            // 寻找最大值
            max = Math.max(max, imax);
        }
        return max;
    }
}

复杂度分析

时间复杂度 $O(N)$ ：N表示数组的长度，遍历一次数组时间 $O(N)$

空间复杂度 $O(1)$ ：仅使用常数级空间变量