leetcode 673 最长递增子序列的个数
创始人
2025-05-29 22:03:57
0次

给定一个未排序的整数数组 nums ， 返回最长递增子序列的个数 。注意这个数列必须是严格递增的。

示例 1:

输入: [1,3,5,4,7]
输出: 2
解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。

示例 2:

输入: [2,2,2,2,2]
输出: 5
解释: 最长递增子序列的长度是1，并且存在5个子序列的长度为1，因此输出5。

这道题可以和 leetcode 300 最长递增子序列进行对比，300这道是求出序列的长度，而这道题考察这样的序列有多少个。

定义dp[i] 表示以 nums[i] 结尾的最长上升子序列的长度，cnt[i] 表示以 nums[i] 结尾的最长上升子序列的个数。dp[i] 之前，我们已经计算出 dp[0…i−1] 的值，则状态转移方程为：
dp[i]=max(dp[j])+1,其中0≤j dp[j] 代表 nums[0…j] 中以 nums[j] 结尾的最长上升子序列。
cnt[i] 等于所有满足 dp[j]+1=dp[i] 的 cnt[j] 之和。

时间复杂度：O(n2)
空间复杂度：O(n)

class Solution:def findNumberOfLIS(self, nums: List[int]) -> int:n, max_len, ans = len(nums), 0, 0dp = [0] * ncnt = [0] * nfor i, x in enumerate(nums):dp[i] = 1cnt[i] = 1for j in range(i):if x > nums[j]:if dp[j] + 1 > dp[i]:dp[i] = dp[j] + 1cnt[i] = cnt[j]  # 重置计数elif dp[j] + 1 == dp[i]:cnt[i] += cnt[j]if dp[i] > max_len:max_len = dp[i]ans = cnt[i]  # 重置计数elif dp[i] == max_len:ans += cnt[i]return ans
词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：【Git从入门到精通】Git基础

下一篇：js逆向学习、安卓逆向

相关内容

热门资讯

首创证券拟赴港上市，“A+H”... 首创证券在A股上市不足三年便启动赴港上市计划。近日，首创证券公告称，公司董事会已审议通过了公司拟发行...
肥东杨大爷要帮“儿子”还钱，银... “儿子”在外借了2万元还不上 “要债人”电话直接打了过来 还？还是不还？ 7月6日 肥东县公安局梁园...
A股上周16家上市公司公布并购... 转自：扬子晚报 扬子晚报网7月27日讯（记者 范晓林 薄云峰）近段时间以来，A股市场并购重组活跃度持...
独家｜某股份行改动零售业务关键... 在资产端信贷“投不动”（多家行零售信贷增速连续几个季度放缓、更有甚者个贷投放负增长）、负债端存款“定...
四川五日游报团指南及详细行程，... 四川，这片位于中国西南的神奇土地，以其独特的自然风光、丰富的文化遗产和诱人的美食而闻名遐迩。从成都的...
原创 中... 在2025年4月初，时任美国总统的特朗普正式启动了针对世界各国的关税战，旨在通过实施经济制裁来促进美...
牛市主升浪开启了？别急！珍惜布... 本周，A股市场上行，主要宽基指数都收获了或多或少的周涨幅，其中，科创50、微盘股涨幅居前。板块方面，...
公募二季报两大看点！港股配置逼... 本报（chinatimes.net.cn）记者栗鹏菲 叶青 北京报道 2025年公募基金二季报披露收...
长和出售港口磋商期或延长 随着可能出现的各方介入及交易结构变化，此次长和港口出售交易如继续进行，其复杂性会提升 文 |《财经》...
中航重机涨0.17%，成交额4... 来源：新浪证券-红岸工作室 7月25日，中航重机涨0.17%，成交额4.14亿元，换手率1.52%，...
重仓电子和新能源行业 【深圳商报讯】（记者 陈燕青）基金二季报出炉，公募二季度依然重仓电子、新能源、食品饮料等行业。公募排...
大婚之后，大笔减持！昔日全球首... 当地时间7月25日，亚马逊公司提交至美国证券交易委员会的文件显示，前全球首富、亚马逊创始人杰夫·贝索...
创源股份涨2.32%，成交额3... 来源：新浪证券-红岸工作室 7月25日，创源股份涨2.32%，成交额3.50亿元，换手率8.32%，...
筹备登陆韩国综合股价指数！大韩... 近日，大韩造船（Daehan Shipbuilding）的首次公开募股（IPO）发行价最终确定为每股...
山东政商要情（7.21—7.2... 记者 王惠 1，2025年上半年山东GDP50046亿元 增长5.6% 7月21日，山东省统计局、国...
《法学基本概念导论》| 专研法... 导言 本书是对权利、义务、法律主体、法律规范、法律渊源、法律行为等法学基本概念（juristic f...
上海AI新动向：世界AI合作组... 在今日的天气状况下，上海迎来了阴到多云的天气，偶尔还有阵雨光顾，气温徘徊在27至31摄氏度之间，给市...
山鹰国际跌1.52%，成交额2... 来源：新浪证券-红岸工作室 7月25日，山鹰国际跌1.52%，成交额2.50亿元，换手率2.33%，...
马斯克擎天柱解决不了无「手」难... 新智元报道 编辑：英智 【新智元导读】马斯克说人形机器人是特斯拉的未来，可今年5000台的目标才刚...
开封警方回应网传“释永信相关警... 7月27日，开封市公安局官方微博回复网友评论时表示：“（网传释永信相关）通报是假的，请不要再传播，目...