每日一道算法之--乘积最大子序和

动态规划指针

Word count: 679Reading time: 2 min

 2020/02/26   Share

乘积最大子序和

力扣第152题:https://leetcode-cn.com/problems/maximum-product-subarray/
给定一个整数数组 nums ，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。

示例 1:

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

示例 2:

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

1. 类似指针的解法

参考力扣第53题最大子序和的其中一种双指针解法,这道题同样可以用类似指针的解法

首先定义一个res记录最大的子序和,cur_pos记录当前的乘积
然后cur_pos依次累乘, 每一次的结果都有三种情况:
- cur_pos等于0, 这时候要重新将指针偏移后一位
- cur_pos大于0, 这时候要更新res的结果,就是和cur_pos比较大小
- cur_pos小于0, 负负得正,需要找到指针前面最大的负数,相除就变为最大

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        if not nums: return 0
        # 目前的累乘
        cur_pro = 1
        # 前面最大的负数
        max_neg = float("-inf")
        # 结果
        res = float("-inf")
        for num in nums:
            cur_pro *= num
            # 考虑三种情况
            # 大于0
            if cur_pro > 0:
                res = max(res, cur_pro)
            # 小于0
            elif cur_pro < 0:
                if max_neg != float("-inf"):
                    res = max(res, cur_pro // max_neg)
                else:
                    res = max(res, num)
                max_neg = max(max_neg, cur_pro)
            # 等于0
            else:
                cur_pro = 1
                max_neg = float("-inf")
                res = max(res, num)
        return res

1.1 复杂度分析

时间复杂度:遍历整个数组的时间复杂度为O(N)
空间复杂度:没有用到额外的数据结构,所以空间复杂度为O(1)

2. 动态规划解决

不难发现,每一个元素的乘积,最大值只可能在自身或者自身与上一次的累乘之中
公式如下:

dp_max[i] = Math.max(nums[i-1],dp_max[i-1]*nums[i-1])

因为存在负数,所以当这个元素为负数是,其最大乘积可能是与上一次最小乘积相乘
所以不仅要定义一个变量存储最大当前的最大累乘,还要定义一个变量存储当前的最小累乘

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        if not nums: return 0
        # 存储最后的结果
        res = nums[0]
        # 存储最大当前的最大累乘
        res_max = nums[0]
        # 存储当前的最小累乘
        res_min = nums[0]
        for num in nums[1:]:
            cur_max = max(res_max*num, res_min*num, num)
            cur_min = min(res_max*num, res_min*num, num)
            res = max(res, cur_max)
            res_max = cur_max
            res_min = cur_min
        return res

2.1 复杂度分析

时间复杂度:遍历整个数组的时间复杂度为O(N)
空间复杂度:没有用到额外的数据结构,所以空间复杂度为O(1)

Author：liangweijiang

原文链接：https://liangweijiang.github.io/2020/02/26/algorithm-152/

发表日期：February 26th 2020, 5:08:00 pm

更新日期：March 2nd 2020, 6:32:21 pm

Next Post

DRF源码解析6--权限组件的封装和初始化
Previous Post

DRF源码解析5--认证组件的封装和初始化

CATALOG

1. 乘积最大子序和
2. 2. 动态规划解决
1. 2.1. 2.1 复杂度分析

