子数组最大乘积

[编程题]子数组最大乘积

热度指数：24199 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

给定一个double类型的数组arr，其中的元素可正可负可0，返回连续子数组累乘的最大乘积。

数据范围：数组大小满足 $0 \le n \le 10$ ，数组中元素满足 $|val| \le 10$

进阶：空间复杂度 $O(1)$ ，时间复杂度 $O(n)$

示例1

输入

[-2.5,4,0,3,0.5,8,-1]

输出

12.00000

说明

取连续子数组[3,0.5,8]可得累乘的最大乘积为12.00000

示例2

输入

[1.0,0.0,0.0]

输出

1.00000

说明

取连续子数组[1.0]可得累乘的最大乘积为1.00000

算法知识视频讲解

Javascript

Tsundere_Map

/**
 * 
 * @param arr double浮点型一维数组 
 * @return double浮点型
 */
function maxProduct( arr ) {
    if(arr.length === 0){
        return 0;
    }
    let maxValues = [arr[0]];
    let minValues = [arr[0]];
    let result = arr[0];
    for(let i = 1; i < arr.length; i++){
        if(arr[i] > 0){
            maxValues[i] = Math.max(arr[i], maxValues[i-1]*arr[i])
            minValues[i] = Math.min(arr[i], minValues[i-1]*arr[i])
        } else {
            maxValues[i] = Math.max(arr[i], minValues[i-1]*arr[i])
            minValues[i] = Math.min(arr[i], maxValues[i-1]*arr[i])
        }
        result = Math.max(result, maxValues[i])
    }
    return result;
}
module.exports = {
    maxProduct : maxProduct
};

发表于 2021-07-23 19:30:07 回复(0)

JavaScript

别卷啦！

这道题题意有bug 怎么不说连续子数组

function maxProduct( arr ) {
    // write code here
    let res = arr[0], arrMin = arr[0], arrMax = arr[0],tempMin = 0, tempMax = 0, len = arr.length
    for(let i = 1;i<len;i++){
        tempMin = arrMin*arr[i]
        tempMax = arrMax*arr[i]
        arrMax = Math.max(tempMin,tempMax,arr[i])
        arrMin  = Math.min(tempMin,tempMax,arr[i])
        res = Math.max(arrMax, res)
    }
    return res
}

编辑于 2021-01-05 17:24:20 回复(0)

JavaScript

Aster_.

js版本累计的乘积

function maxProduct( arr ) {
    // write code here
    // 如果数组里面有0或者负数的情况，会影响到数的大小
    let min = arr[0];
    let max = min;//一开始的数
    let res = max;
    for(let i=1;i<arr.length;i++){
        let last_max = max,last_min = min;
        min = Math.min(arr[i],arr[i]*last_min,arr[i]*last_max);//最小的数肯定是从这几个地方来的
        max = Math.max(arr[i],arr[i]*last_max,arr[i]*last_min);
        res = Math.max(res,max)
    }
    return res;  
}

发表于 2020-08-31 15:36:39 回复(0)