博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
Leetcode 152. Maximum Product Subarray javascript解决方案
阅读量:6387 次
发布时间:2019-06-23

本文共 2020 字,大约阅读时间需要 6 分钟。

题意

给一串整数,可能为正数、负数、0,求连续一串能得到的最大积。

思路

根据0来断开一个个子串分别处理。 子串处理方式:子串全部相乘,因为没有小数,如果结果为正数,则返回乘积,负数就从左数和从右数,数到负数结束,看那边得到的数值更小,也就是负数更负,把乘积除以这个左右数中更小的值,就是这个子串的最大乘积。

选出子串中的最大返回值。
几个特殊情况:
数组长度为1,返回第一个

代码:

/** * @param {number[]} nums * @return {number} */var maxProduct = function(nums) {    /**     * @param {number[]} non 0 number list     * @return {number} max product     */    function handleNonZeroList(list){        if(list.length < 2){            return list[0];        }        let productTotal = 1;        list.forEach(obj => {            productTotal *= obj;        });        if(productTotal > 0){            return productTotal;        }        let leftProduct = 1, leftMinus = -1;        for(let i = 0;i < list.length; ++i){            if(list[i] < 0){                leftMinus = list[i];                break;            }            leftProduct *= list[i];        }        leftProduct *= leftMinus;        let rightProduct = 1, rightMinus = -1;        for(let i = list.length - 1;i >= 0; --i){            if(list[i] < 0){                rightMinus = list[i];                break;            }            rightProduct *= list[i];        }        rightProduct *= rightMinus;        return productTotal /= (leftProduct > rightProduct ? leftProduct : rightProduct);    }    if(nums.length < 2){        return nums[0];    }    let arrays = [], tmpList = [], hasZero = false;    for(let i = 0;i < nums.length; ++i){        if(nums[i] === 0){            hasZero = true;            if(tmpList.length > 0){                arrays.push(tmpList);                tmpList = [];            }        }        else{            tmpList.push(nums[i]);        }    }    if(tmpList.length > 0){        arrays.push(tmpList);        tmpList = [];    }    let max = 0;    for(let i = 0; i < arrays.length; ++i){        let tmp = handleNonZeroList(arrays[i]);        if(tmp > max){            max = tmp;        }    }    if(max < 0 && hasZero){        return 0;    }    return max;};复制代码

转载于:https://juejin.im/post/5a5c8d54518825732d7f9530

你可能感兴趣的文章
freemarker自定义标签的写法和使用
查看>>
使用Gitlab CI进行持续集成
查看>>
Win32编程基本概念
查看>>
×××灯式样的站点链接说明,链接提示
查看>>
Linux下动态IP和静态IP的设置方法
查看>>
mysql 行长度
查看>>
SUSE配置网关
查看>>
java中获取字母和数字的组合
查看>>
8-3 泛型
查看>>
你是“职业”软件开发吗?——书评《浮现式设计-专业软件开发的演进本质》...
查看>>
iOS 多线程 之 GCD(大中枢派发)(二)
查看>>
开源项目 log4android 使用方式详解
查看>>
ssh命令详解
查看>>
C# 中字符串转换成日期
查看>>
垃圾短信相关用户细分方案
查看>>
免费的Windows系统工具
查看>>
脚本:将git项目下载到本地并启动
查看>>
Linked List Cycle && Linked List Cycle II
查看>>
SeleniumTest
查看>>
ubuntu10.04 交叉编译 aria2 总结
查看>>