LeetCode-152. 乘积最大子数组【数组 动态规划】

2024-04-13 18:12

本文主要是介绍LeetCode-152. 乘积最大子数组【数组 动态规划】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

LeetCode-152. 乘积最大子数组【数组 动态规划】

  • 题目描述:
  • 解题思路一:动态规划五部曲:定推初遍举
  • 解题思路二:因为每一个状态只与前一个状态有关,可以使用「滚动变量」技巧,使用常数个变量完成这道问题。
  • 解题思路三:0

题目描述:

给你一个整数数组 nums ,请你找出数组中乘积最大的非空连续
子数组
(该子数组中至少包含一个数字),并返回该子数组所对应的乘积。

测试用例的答案是一个 32-位 整数。

示例 1:

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

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

提示:

1 <= nums.length <= 2 * 104
-10 <= nums[i] <= 10
nums 的任何前缀或后缀的乘积都 保证 是一个 32-位 整数

解题思路一:动态规划五部曲:定推初遍举

  1. dp定义
    以下标 i 结尾的连续子序列的乘积的最大值。
    牢记状态的定义,一定以下标 i 结尾,即:乘积数组中 nums[i] 必须被选取。
    • 如果 dp[i - 1] 是负数,乘上 nums[i] 还是负数,倒不如另起炉灶。
    • 如果 nums[i] 是负数该怎么办呢?dp[i - 1] 是正数的时候,越乘越小,dp[i - 1] 是负数的时候,越乘越大,于是我们可能就需要记录一下负数的那个最小数。

遇到这样的问题,其实就在提示我们状态不够用了。因此,需要在原来的一维 dp 后面新增一个状态。

针对这道题,第 2 维状态只需要两个:

  • 用 0 表示遍历的过程中得到的以 nums[i] 结尾的连续子序列的乘积的最小值;
  • 用 1 表示遍历的过程中得到的以 nums[i] 结尾的连续子序列的乘积的最大值。

当 nums[i] = 0 的时候包含在上面二者之中,无需单独讨论。

状态转移方程写在了参考代码 1 中。即使用二维状态数组同时记录乘积的最大值和最小值,本来写了一堆文字的,后来看太长了,好多废话,直接看代码比较清楚一些。

这里就声明一下状态:

dp[i][1] 表示:以 nums[i] 结尾的连续子序列的乘积的最大值;
dp[i][0] 表示:以 nums[i] 结尾的连续子序列的乘积的最小值。

  1. 推导公式
if nums[i] >= 0:dp[i][1] = max(nums[i], dp[i-1][1] * nums[i])dp[i][0] = min(nums[i], dp[i-1][0] * nums[i])else:dp[i][1] = max(nums[i], dp[i-1][0] * nums[i])dp[i][0] = max(nums[i], dp[i-1][1] * nums[i])
  1. 初始化
dp = [[0, 0] for _ in range(n)]dp[0][0] = nums[0]dp[0][1] = nums[0]
  1. 遍历顺序,显然是从前往后
for i in range(1, n):
  1. 举例
    在这里插入图片描述
class Solution:def maxProduct(self, nums: List[int]) -> int:n = len(nums)if n == 0:return 0dp = [[0, 0] for _ in range(n)]dp[0][0] = nums[0]dp[0][1] = nums[0]for i in range(1, n):if nums[i] >= 0:dp[i][1] = max(nums[i], dp[i-1][1] * nums[i])dp[i][0] = min(nums[i], dp[i-1][0] * nums[i])else:dp[i][1] = max(nums[i], dp[i-1][0] * nums[i])dp[i][0] = min(nums[i], dp[i-1][1] * nums[i])# print(dp)ans = dp[0][1]for i in range(1, n):ans = max(ans, dp[i][1])return ans

时间复杂度:O(n)
空间复杂度:O(n)

解题思路二:因为每一个状态只与前一个状态有关,可以使用「滚动变量」技巧,使用常数个变量完成这道问题。

class Solution:def maxProduct(self, nums: List[int]) -> int:n = len(nums)if n == 0:return 0# dp = [[0, 0] for _ in range(n)]# dp[0][0] = nums[0]# dp[0][1] = nums[0]preMax = nums[0]preMin = nums[0]curMax = preMaxcurMin = preMinans = nums[0]for i in range(1, n):if nums[i] >= 0:curMax = max(nums[i], preMax * nums[i])curMin = min(nums[i], preMin * nums[i])else:curMax = max(nums[i], preMin * nums[i])curMin = min(nums[i], preMax * nums[i])ans = max(ans, curMax)# 滚动变量preMax = curMaxpreMin = curMinreturn ans

时间复杂度:O(n)
空间复杂度:O(1)

解题思路三:0


时间复杂度:O(n)
空间复杂度:O(n)

这篇关于LeetCode-152. 乘积最大子数组【数组 动态规划】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/900853

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

第10章 中断和动态时钟显示

第10章 中断和动态时钟显示 从本章开始,按照书籍的划分,第10章开始就进入保护模式(Protected Mode)部分了,感觉从这里开始难度突然就增加了。 书中介绍了为什么有中断(Interrupt)的设计,中断的几种方式:外部硬件中断、内部中断和软中断。通过中断做了一个会走的时钟和屏幕上输入字符的程序。 我自己理解中断的一些作用: 为了更好的利用处理器的性能。协同快速和慢速设备一起工作

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

动态规划---打家劫舍

题目: 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。 思路: 动态规划五部曲: 1.确定dp数组及含义 dp数组是一维数组,dp[i]代表

hdu 1166 敌兵布阵(树状数组 or 线段树)

题意是求一个线段的和,在线段上可以进行加减的修改。 树状数组的模板题。 代码: #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while

软考系统规划与管理师考试证书含金量高吗?

2024年软考系统规划与管理师考试报名时间节点: 报名时间:2024年上半年软考将于3月中旬陆续开始报名 考试时间:上半年5月25日到28日,下半年11月9日到12日 分数线:所有科目成绩均须达到45分以上(包括45分)方可通过考试 成绩查询:可在“中国计算机技术职业资格网”上查询软考成绩 出成绩时间:预计在11月左右 证书领取时间:一般在考试成绩公布后3~4个月,各地领取时间有所不同

poj 3723 kruscal,反边取最大生成树。

题意: 需要征募女兵N人,男兵M人。 每征募一个人需要花费10000美元,但是如果已经招募的人中有一些关系亲密的人,那么可以少花一些钱。 给出若干的男女之间的1~9999之间的亲密关系度,征募某个人的费用是10000 - (已经征募的人中和自己的亲密度的最大值)。 要求通过适当的招募顺序使得征募所有人的费用最小。 解析: 先设想无向图,在征募某个人a时,如果使用了a和b之间的关系

poj 2976 分数规划二分贪心(部分对总体的贡献度) poj 3111

poj 2976: 题意: 在n场考试中,每场考试共有b题,答对的题目有a题。 允许去掉k场考试,求能达到的最高正确率是多少。 解析: 假设已知准确率为x,则每场考试对于准确率的贡献值为: a - b * x,将贡献值大的排序排在前面舍弃掉后k个。 然后二分x就行了。 代码: #include <iostream>#include <cstdio>#incl

poj 3258 二分最小值最大

题意: 有一些石头排成一条线,第一个和最后一个不能去掉。 其余的共可以去掉m块,要使去掉后石头间距的最小值最大。 解析: 二分石头,最小值最大。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <c

poj 2175 最小费用最大流TLE

题意: 一条街上有n个大楼,坐标为xi,yi,bi个人在里面工作。 然后防空洞的坐标为pj,qj,可以容纳cj个人。 从大楼i中的人到防空洞j去避难所需的时间为 abs(xi - pi) + (yi - qi) + 1。 现在设计了一个避难计划,指定从大楼i到防空洞j避难的人数 eij。 判断如果按照原计划进行,所有人避难所用的时间总和是不是最小的。 若是,输出“OPETIMAL",若