Leetcode日记_01,乘积最大子序列

栏目: 编程工具 · 发布时间: 5年前

内容简介:给定一个整数数组 nums ,找出一个序列中乘积最大的连续子序列(该序列至少包含一个数)。示例 1:输入: [2,3,-2,4]

题目

乘积最大子序列

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

示例 1:

输入: [2,3,-2,4]

输出: 6

解释: 子数组 [2,3] 有最大乘积 6。

示例 2:

输入: [-2,0,-1]

输出: 0

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

我的解题思路

暴力法

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        max = nums[0]
        for i in range(len(nums)):
            prod = 1
            for j in range(i, len(nums)):
                prod *= nums[j]
                if prod > max:
                    max = prod
        return max

执行代码 OK通过

我们再自行测试一遍

先将测试用例改为[-2], OK也没问题

如果测试用例非常长,那么该方法肯定不可取,因为其时间复杂度为O(n^2)

leetcode上的范例

class Solution:
    def maxProduct(self, nums: list) -> int:
        B = nums[::-1]
        for i in range(1, len(nums)):
            nums[i] *= nums[i - 1] or 1
            B[i] *= B[i - 1] or 1
        return max(max(nums), max(B))

这个方法我有点搞不明白

按理来说 设nums中元素个数为x,则理论上应该有

$$ \sum_{i=1}^x x = \frac{1}{2} x^2 + \frac{1}{2} x $$

个非空子序列,而上面这个方法中 numsB 仅列出了 x+x=2x 个非空子序列

动态规划

状态定义:

f(x) -------- nums数组中[0, x]范围内的最大连续子序列的乘积,且该连续子序列以nums[x]结尾

g(x) -------- nums数组中[0, x]范围内的最小连续子序列的乘积,且该连续子序列以nums[x]结尾

状态转移:

(1)当x等于0时,显然此时[0, x]范围内只有一个元素,f(0)和g(0)均等于这个唯一的元素。

(2)当x大于0时

a:如果nums[x] >= 0,f(x) = max(f(x - 1) nums[x], nums[x]),g(x) = min(g(x - 1) nums[x], nums[x])

b:如果nums[x] < 0,f(x) = max(g(x - 1) nums[x], nums[x]),g(x) = min(f(x - 1) nums[x], nums[x])

时间复杂度和空间复杂度均为O(n),其中n是nums数组中的元素个数。

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        maxpd = []
        minpd = []
        for i in range(len(nums)):
            if i == 0:
                maxpd.append(nums[0])
                minpd.append(nums[0])
            else:
                if nums[i] >= 0:
                    maxpd.append(max(maxpd[i-1]*nums[i], nums[i]))
                    minpd.append(min(minpd[i-1]*nums[i], nums[i]))
                else:
                    maxpd.append(max(minpd[i-1]*nums[i], nums[i]))
                    minpd.append(min(maxpd[i-1]*nums[i], nums[i]))
        return max(maxpd)

动态规划法参考自 https://blog.csdn.net/qq_4123...


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

ASP.NET 2.0入门经典

ASP.NET 2.0入门经典

哈特 / 清华大学出版社 / 2006-8 / 78.00元

该书是Wrox红皮书中的畅销品种, 从初版、1.0版、1.1版到目前的2.0版,已经3次升级,不仅内容更加完善、实用,还展现了.NET 2.0的最新技术和ASP.NET 2.0最新编程知识,是各种初学者学习ASP.NET的优秀教程,也是Web开发人员了解ASP.NET 2.0新技术的优秀参考书。该书与《ASP.NET 2.0高级编程(第4版)》及其早期版本,曾影响到无数中国Web程序员。一起来看看 《ASP.NET 2.0入门经典》 这本书的介绍吧!

HTML 编码/解码
HTML 编码/解码

HTML 编码/解码

SHA 加密
SHA 加密

SHA 加密工具

XML、JSON 在线转换
XML、JSON 在线转换

在线XML、JSON转换工具