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

justjavac 发布于2019-07-31 10:36 / 2060人阅读

摘要：题目乘积最大子序列给定一个整数数组，找出一个序列中乘积最大的连续子序列该序列至少包含一个数。示例输入输出解释结果不能为因为不是子数组。当大于时如果，，如果，，时间复杂度和空间复杂度均为，其中是数组中的元素个数。动态规划法参考自

题目 乘积最大子序列

给定一个整数数组 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 $$

个非空子序列,而上面这个方法中nums和B仅列出了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...

云服务器海外云主机最大子序列 leetcode_35_SearchIn 最长递增子序列最长公共子序列

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/44090.html

leetcode152 Maximum Product Subarray

摘要：题目要求从一个整数数组中找到一个子数组，该子数组中的所有元素的乘积最大。比如数组的最大乘积子数组为思路与代码这题目考察了动态编程的思想。至于为什么还要比较，是因为如果是一个负数的，那么之前的最小乘积在这里可能就成为了最大的乘积了。题目要求 Find the contiguous subarray within an array (containing at least one num...

Arno 2019-08-16 10:57 评论0 收藏0
小李飞刀：做题第八弹！

摘要：认真做题的分割线第一题乘积最大子序列难度中等给定一个整数数组，找出一个序列中乘积最大的连续子序列该序列至少包含一个数。写在前面的话慢慢转变思路，不再死磕不会做的题，思路可以先借鉴，但是一定要吃透透。上周末看完看完了《算法图解》，感觉对一些题目的思路有比较大的帮助，但是还是要在实践中理解。认真做题的分割线第一题 152. 乘积最大子序列难度：中等给定一个整数数组nums，找出一个...

ztyzz 2019-07-31 10:11 评论0 收藏0
前端 | 每天一个 LeetCode

摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。在线网站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公众号： showImg(htt...

张汉庆 2019-08-23 13:42 评论0 收藏0
LeetCode 343. Integer Break

摘要：思路动态规划，前五个数的最大乘积为，后面的第个数的最大乘积，由从后往前数包括本身的第三个数乘以得到。何睿何睿前个数的最大乘积动态规划第个数的最大乘积为往前数第三个数思路与上面的思路一致，优化了空间源代码文件在这里。 Description Given a positive integer n, break it into the sum of at least two positive...

ckllj 2019-07-31 10:17 评论0 收藏0
leetcode-300-Longest Increasing Subsequence

摘要：本质找出最长的递增子序列的长度，可以是不连续的。应用判断满足一定条件的子序列的最大长度，用动态数组加以处理。二分法确定满足条件的位置。类似二分法查找元素，查找某种情况的子序列。本质：找出最长的递增子序列的长度，可以是不连续的。用一个数组存储递增子序列，遍历原始数组，每增加一个数，往里添加到对应的顺序，记录他的位置，即为此数组的长度。成立的理由：每一个数添加以后，都有对...

amc 2019-07-30 17:36 评论0 收藏0