Leetcode-152. 乘积最大子序列

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

示例 1:

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

示例 2:

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

解法：1. 使用暴力解法。2. 使用dp策略，首先要做的还是定义dp[i][0]状态的含义，这里的状态指的是i位置向左，必须包含i的情况下，能够获得的最大值，相应的dp[i][0]指的就是包含i时向左能够获得的最小值，然后定义状态转移方程，如下图所示，也就是需要根据a[i]的值来进行调整。

  • Java 
class Solution {
   
    public int maxProduct(int[] nums) {
   
        // 只需要用到dp[i-1]和dp[i]，所以一直维持两个值存储dp[i-1]的最大最小值就可以了
        int curMin = nums[0], curMax = nums[0], res = nums[0];
        for (int i=1;i<nums.length;i++) {
   
            int tmp1 = nums[i]*curMax;
            int tmp2 = nums[i]*curMin;
            curMax = Math.max(tmp1>=tmp2?tmp1:tmp2, nums[i]);
            curMin = Math.min(tmp1>=tmp2?tmp2:tmp1, nums[i]);
            res = curMax>res?curMax:res;
        }
        return res;
    }
}
  • Python 
class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        curMin, curMax, res = nums[0],nums[0],nums[0]
        for i in range(1, len(nums)):
            tmp1 = nums[i]*curMax
            tmp2 = nums[i]*curMin
            curMax = max(tmp1,tmp2,nums[i])
            curMin = min(tmp1,tmp2,nums[i])
            res = curMax if curMax>res else res
        return res