当前位置: 首页 > article >正文

LeetCode 152. 乘积最大子数组

LeetCode 152. 乘积最大子数组

给你一个整数数组 nums ,请你找出数组中乘积最大的非空连续 子数组(该子数组中至少包含一个数字),并返回该子数组所对应的乘积。
测试用例的答案是一个 32-位 整数。
示例 1:
输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
输入: nums = [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
提示:
1 <= nums.length <= 2 * 104
-10 <= nums[i] <= 10
nums 的任何子数组的乘积都 保证 是一个 32-位 整数

动态规划

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        # s[i] 表示以 nums[i] 结尾的乘积最小的数组的乘积大小
        # g[i] 表示以 nums[i] 结尾的乘积最大的数组的乘积大小
        # s[i] = min{s[i-1] * nums[i], g[i-1] * nums[i], nums[i]}
        # g[i] = max{s[i-1] * nums[i], g[i-1] * nums[i], nums[i]}

        s, g = [sys.maxsize] * len(nums), [-sys.maxsize] * len(nums)
        s[0] = g[0] = nums[0]
        for i in range(1, len(nums)):
            s[i] = min(s[i - 1] * nums[i], g[i - 1] * nums[i], nums[i])
            g[i] = max(s[i - 1] * nums[i], g[i - 1] * nums[i], nums[i])
        return max(g)

时间复杂度:O(n)
空间复杂度:O(n)

优化方案,由于状态转移方程中当前状态仅仅依赖于上一个状态,所以数组可以压缩为一个变量,O(n)可以优化为O(1)

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        # s[i] 表示以 nums[i] 结尾的乘积最小的数组的乘积大小
        # g[i] 表示以 nums[i] 结尾的乘积最大的数组的乘积大小
        # s[i] = min{s[i-1] * nums[i], g[i-1] * nums[i], nums[i]}
        # g[i] = max{s[i-1] * nums[i], g[i-1] * nums[i], nums[i]}

        res = s = g = nums[0]
        for i in range(1, len(nums)):
            _s = min(s * nums[i], g * nums[i], nums[i])
            _g = max(s * nums[i], g * nums[i], nums[i])
            s, g = _s, _g
            res = max(res, g)
        return res

时间复杂度:O(n)
空间复杂度:O(1)


http://www.kler.cn/a/329326.html

相关文章:

  • OSRM docker环境启动
  • 金山云Q3调整后EBITDA率提升至9.8% 经营效率和盈利能力强劲增长
  • 【python】Bokeh 与 Plotly:创建交互式数据可视化工具
  • K8S资源限制之resources
  • Java putIfAbsent() 详解
  • MySQL 怎么不丢数据(关于开启双1配置)
  • TIM(Timer)定时器的原理
  • 深入浅出SpringBoot框架
  • Python 在区块链智能合约开发中的应用与实践
  • 土地规划与区域经济发展:筑基均衡未来的战略经纬
  • MongoDB 工具包安装(mongodb-database-tools)
  • (27)oracle镜像启动
  • 【更新】红色文化之红色博物馆数据集(经纬度+地址)
  • 用Promise实现前端并发请求
  • Win10鼠标总是频繁自动失去焦点-非常有效-重启之后立竿见影
  • Bigemap Pro首发(一款真正全面替代Arcgis的国产基础软件)
  • Linux Mint急救模式
  • 英伟达Ampere架构和Hopper架构技术解析
  • C++(Qt)软件调试---内存调试器Dr.Memory(21)
  • 模拟实战数据落地:MSsql通过存储过程获得销售数据视图
  • Ubuntu20.04中ros2 foxy版本安装gazebo,并运行小车运动demo
  • Java中使用接口实现回调函数的详解与示例
  • C语言、Eazy_X——五子棋
  • 零知识证明在BSV网络上的应用
  • 高度细化的SAGA模式实现:基于Spring Boot与RabbitMQ的跨服务事务
  • 甄选范文“论软件的可靠性设计”,软考高级论文,系统架构设计师论文