内容简介:给定一个整数数组 nums ,找出一个序列中乘积最大的连续子序列(该序列至少包含一个数)。示例 1:输入: [2,3,-2,4]
题目
乘积最大子序列
给定一个整数数组 nums ,找出一个序列中乘积最大的连续子序列(该序列至少包含一个数)。
示例 1:
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
我的解题思路
暴力法
class Solution: def maxProduct(self, nums: List[int]) -> int: max = nums[0] for i in range(len(nums)): prod = 1 for j in range(i, len(nums)): prod *= nums[j] if prod > max: max = prod return max
执行代码 OK通过
我们再自行测试一遍
先将测试用例改为[-2], OK也没问题
如果测试用例非常长,那么该方法肯定不可取,因为其时间复杂度为O(n^2)
leetcode上的范例
class Solution: def maxProduct(self, nums: list) -> int: B = nums[::-1] for i in range(1, len(nums)): nums[i] *= nums[i - 1] or 1 B[i] *= B[i - 1] or 1 return max(max(nums), max(B))
这个方法我有点搞不明白
按理来说 设nums中元素个数为x,则理论上应该有
$$ \sum_{i=1}^x x = \frac{1}{2} x^2 + \frac{1}{2} x $$
个非空子序列,而上面这个方法中 nums 和 B 仅列出了 x+x=2x 个非空子序列
动态规划
状态定义:
f(x) -------- nums数组中[0, x]范围内的最大连续子序列的乘积,且该连续子序列以nums[x]结尾
g(x) -------- nums数组中[0, x]范围内的最小连续子序列的乘积,且该连续子序列以nums[x]结尾
状态转移:
(1)当x等于0时,显然此时[0, x]范围内只有一个元素,f(0)和g(0)均等于这个唯一的元素。
(2)当x大于0时
a:如果nums[x] >= 0,f(x) = max(f(x - 1) nums[x], nums[x]),g(x) = min(g(x - 1) nums[x], nums[x])
b:如果nums[x] < 0,f(x) = max(g(x - 1) nums[x], nums[x]),g(x) = min(f(x - 1) nums[x], nums[x])
时间复杂度和空间复杂度均为O(n),其中n是nums数组中的元素个数。
class Solution: def maxProduct(self, nums: List[int]) -> int: maxpd = [] minpd = [] for i in range(len(nums)): if i == 0: maxpd.append(nums[0]) minpd.append(nums[0]) else: if nums[i] >= 0: maxpd.append(max(maxpd[i-1]*nums[i], nums[i])) minpd.append(min(minpd[i-1]*nums[i], nums[i])) else: maxpd.append(max(minpd[i-1]*nums[i], nums[i])) minpd.append(min(maxpd[i-1]*nums[i], nums[i])) return max(maxpd)
动态规划法参考自 https://blog.csdn.net/qq_4123...
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:- 力扣152——乘积最大子序列
- 蓝桥杯 ADV-189 算法提高 连接乘积
- 算法 - 找出数组中子集乘积的最大值
- 蓝桥杯 ADV-13 算法提高 最小乘积(提高型)
- LeetCode每日一题: 三个数的最大乘积(No.628)
- Java 序列化反序列化对比
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
JavaScript高级程序设计:第2版
Nicholas Zakas / 李松峰、曹力 / 人民邮电出版社 / 2010-7 / 89.00元
《JavaScript高级程序设计(第2版)》在上一版基础上进行了大幅度更新和修订,融入了近几年来JavaScript应用发展的最新成果,几乎涵盖了所有需要理解的重要概念和最新的JavaScript应用成果。从颇具深度的JavaScript语言基础到作用域(链),从引用类型到面向对象编程,从极其灵活的匿名函数到闭包的内部机制,从浏览器对象模型(BOM)、文档对象模型(DOM)到基于事件的Web脚本......一起来看看 《JavaScript高级程序设计:第2版》 这本书的介绍吧!