152. 乘积最大子序列

题目描述

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

示例

示例 1:

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

示例 2:

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

思路

本题主要考虑使用动态规划的方法进行求解。

第一步，定义状态。设 DP[i] 为前 i 个数中的乘积最大子序列，其最大值应从 DP[i-1] 的最大值乘上 nums[i] 中取，这时需要考虑 nums[i] 的正负，若 nums[i] 为正，则 DP[i] 为 DP[i-1] 的最大值乘以 nums[i] ，否则为 DP[i-1] 的最大负值乘以 nums[i] 。所以，跟以往不同，本题的状态定义需要用到二维数组，即 DP[i][0] 存储前 i 个数中乘积正值最大子序列，DP[i][1] 存储前 i 个数中乘积负值最大子序列。

第二步，获得状态转移方程。 当然，本题的状态转移方程也是分为两种的。

if a[i] > 0: DP[i][0] = DP[i-1][0] * a[i] DP[i][1] = DP[i-1][1] * a[i] else: DP[i][1] = DP[i-1][0] * a[i] DP[i][0] = DP[i-1][1] * a[i]

代码为：

class Solution(object): def maxProduct(self, nums): """ :type nums: List[int] :rtype: int """ if nums is None: return 0 dp = [[0 for _ in range(2)] for _ in range(2)] dp[0][1], dp[0][0], res = nums[0], nums[0], nums[0] for i in range(1, len(nums)): x, y = i % 2, (i-1) % 2 dp[x][0] = max(dp[y][0] * nums[i], dp[y][1] * nums[i], nums[i]) dp[x][1] = min(dp[y][0] * nums[i], dp[y][1] * nums[i], nums[i]) res = max(res, dp[x][0]) return res

上面代码运用了滚动数组的思想以降低空间复杂度，将原本 2*len(nums) 大小的二维数组转成了 2*2 大小的二维数组。当然该数组也可直接用变量直接代替，此时代码如下：

class Solution(object): def maxProduct(self, nums): """ :type nums: List[int] :rtype: int """ if nums is None: return 0 res, cur_max, cur_min = nums[0], nums[0], nums[0] for i in range(1, len(nums)): num = nums[i] cur_max, cur_min = cur_max * num, cur_min * num cur_min, cur_max = min(cur_max, cur_min, num), max(cur_max, cur_min, num) res = cur_max if cur_max > res else res return res

GitHub地址：https://github.com/protea-ban/LeetCode

转载于:https://www.cnblogs.com/banshaohuan/p/11507044.html

相关资源：JAVA上百实例源码以及开源项目