题目
乘积最大子序列
给定一个整数数组 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…