[LeetCode]152 乘积最大子序列

题目描述

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

示例1

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

示例2

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

思路

  • 经典动态规划
  • 先计算从左到右的相乘的最大值，再计算从右到左的最大值；再将两组最大值相比

代码

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
    def maxProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums_re = nums[::-1]
        for i in range(1, len(nums)):
            nums[i] *= nums[i - 1] or 1
            nums_re[i] *= nums_re[i - 1] or 1
        return max(max(nums),max(nums_re))