题目大意
#
给定一个整数数组 nums,要求找出数组中乘积最大的连续子数组(最少包含一个数字),并返回该子数组对应的乘积。
解题思路
#
这道题跟「
0053. 最大子序和」有点相似,不过一个求的是和的最大值,这道题求解的是乘积的最大值。
乘积有个特殊情况,两个正数、两个负数相乘都会得到正数。所以求解的时候需要考虑负数的情况。
若想要最终的乘积最大,则应该使子数组中的正数元素尽可能的大,负数元素尽可能的小。所以可以维护一个最大值变量和最小值变量。
动态规划的状态可写为: $dp_{max}[i]$ 表示为以第 i 个元素结尾的乘积最大子数组的乘积,$dp_{min}[i]$ 表示为以第 i 个元素结尾的乘积最小子数组的乘积。
动态规划的状态转移方程可以写成:
- $dp_{max}[i] = max(dp_{max}[i-1] * nums[i], nums[i], dp_{min}[i-1] * nums[i])$
- $dp_{min}[i] = min(dp_{min}[i-1] * nums[i], nums[i], dp_{max}[i-1] * nums[i])$
最后找出 $dp_{max}$ 中最大值即为乘积最大子数组的乘积。
当然,因为状态转移方程中只涉及到当前元素和前一个元素,所以我们也可以不使用数组,只使用两个变量来维护 $dp_{max}[i]$ 和 $dp_{min}[i]$。可参考「2. 解法二」的代码。
代码
#
- 解法一
1
2
3
4
5
6
7
8
9
10
11
12
|
class Solution:
def maxProduct(self, nums: List[int]) -> int:
size = len(nums)
dp_max = [0 for _ in range(size)]
dp_min = [0 for _ in range(size)]
dp_max[0] = nums[0]
dp_min[0] = nums[0]
ans = nums[0]
for i in range(1, size):
dp_max[i] = max(dp_max[i-1] * nums[i], nums[i], dp_min[i-1] * nums[i])
dp_min[i] = min(dp_min[i-1] * nums[i], nums[i], dp_max[i-1] * nums[i])
return max(dp_max)
|
- 解法二
1
2
3
4
5
6
7
8
9
10
11
12
|
class Solution:
def maxProduct(self, nums: List[int]) -> int:
size = len(nums)
max_num, min_num = nums[0], nums[0]
ans = nums[0]
for i in range(1, size):
temp_max = max_num
temp_min = min_num
max_num = max(temp_max * nums[i], nums[i], temp_min * nums[i])
min_num = min(temp_min * nums[i], nums[i], temp_max * nums[i])
ans = max(max_num, ans)
return ans
|