【搞定算法】子数组最大累乘积

ゝ一世哀愁。 2021-11-23 08:40 326阅读 0赞

> 博主秋招提前批已拿百度、字节跳动、拼多多、顺丰等公司的offer，可加微信：**pcwl\_Java** 一起交流秋招面试经验，可获得博主的秋招简历和复习笔记。

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

*  ** 子数组问题套路**

> **在某种标准/条件下求子数组中最大/最小/最优的解法：****在标准下，求解以每个 i 位置作为开头或者结尾的子数组的答案，那么全局的答案一定在其中。**

**分析：**

**本题求以每个位置 i 结尾的子数组的最大累乘积是多少，如果你每个位置都求出来了，答案一定在其中。**

必须以 i 位置结尾的子数组的最大累乘积是多少，列可能性：

1、以 i 结尾的子数组自己是一个子数组，不往左扩，即只含 i；

2、以 i 结尾的子数组往左扩；

*  2.1、当 arr\[i\] > 0，最大累乘积是 i - 1 位置的最大累乘积 \* arr\[i\]；
 *  2.2、当 arr\[i\] < 0，最大累乘积是 i - 1 位置的最小累乘积 \* arr\[i\]；

**所以对每个位置，我们都需要得到以该位置结尾的最大累乘积和最小累乘积。**

public class MaxMulitiple {
    
        public static double maxMulitiple(double[] arr){
            if(arr == null || arr.length == 0){
                return 0;
            }
    
            double max = arr[0];  // 记录以i位置结尾的最大累乘积
            double min = arr[0];  // 记录以i位置结尾的最小累乘积
            double res = arr[0];  // 最后的结果
            // 记录以i位置结尾的三种情况下的累乘积
            double possible1 = 0;
            double possible2 = 0;
            double possible3 = 0;
            // 从1开开始作为子数组的结尾，依次往后遍历每个元素作为子数组结尾的情况
            for(int i = 1; i < arr.length; i++){
                // 情况1：i位置自己是一个子数组
                possible1 = arr[i];
                // 情况2： arr[i] > 0.i位置作为子数组的结尾，往左扩 i-1位置最大累乘积
                possible2 = max * arr[i];
                // 情况3： arr[i] < 0.i位置作为子数组的结尾，往左扩 i-1位置最小累乘积
                possible3 = min * arr[i];
                // 三种情况最大和最小
                max = Math.max(Math.max(possible1,possible2), possible3);
                min = Math.min(Math.min(possible1,possible2), possible3);
                res = Math.max(max, res);
            }
            return res;
        }
    }