[LeetCode]152. 乘积最大子序列(Maximum Product Subarray)

题目描述

给定一个整数数组 nums ,找出一个序列中乘积最大的连续子序列(该序列至少包含一个数)。

示例 1:

输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

示例 2:

输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

解题思路

使用动态规划的思想,用数组来存储到目前为止最大的连续乘积,由于乘法对于符号的特殊性,最大的乘积乘以一个负数会变成最小,所以需要同时维护一个到目前为止最小乘积的数组,当遇到负数时,使用对方的最后一个数值进行计算。

代码

Python 3.6

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def maxProduct(self, nums: List[int]) -> int:
length = len(nums)
dp_max, dp_min = [0] * length, [0] * length
dp_max[0], dp_min[0] = nums[0], nums[0]
for i in range(1, length):
if nums[i] < 0:
dp_max[i] = max(dp_min[i - 1] * nums[i], nums[i])
dp_min[i] = min(dp_max[i - 1] * nums[i], nums[i])
else:
dp_max[i] = max(dp_max[i - 1] * nums[i], nums[i])
dp_min[i] = min(dp_min[i - 1] * nums[i], nums[i])
return max(max(dp_max), max(dp_min))