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逆向学习、安卓逆向

相关内容

热门资讯

现货黄金直线跳水，跌破5200... 新闻荐读 1月29日晚，现货黄金白银快速走低，回吐盘中全部涨幅。23:15左右，现货黄金跌破5300...
加拿大拟与多国联合设立国防银行 新华社北京1月31日电　加拿大财政部长商鹏飞1月30日说，加拿大将在未来数月与国际伙伴密切合作，推进...
马斯克大消息！SpaceX申请... 据券商中国，美东时间1月30日，路透社报道，据两位知情人士透露，马斯克旗下SpaceX公司2025年...
澳网：雷巴金娜2-1萨巴伦卡女... 北京时间1月31日，2026赛季网球大满贯澳大利亚公开赛继续进行，在女单决赛中，5号种子雷巴金娜6-...
春节前白酒促销热：“扫码抽黄金... 春节临近，白酒市场再现价格异动。 近日，飞天茅台批价拉升，有酒商直言“年前要冲2000元关口”，引发...
新安县人民医院让专业护理走进千... 由211名专业人员组成的服务团队，提供60项全维度服务，累计完成上门服务3217人次；实现“入院—出...
跨国企业负责人高度肯定中国经济... 本文转自【中国经济网-《经济日报》】； 参观者在第八届中国国际进口博览会美敦力公司一款超硬导丝产品...
中药配方颗粒标准化浪潮：数商云... 在中医药现代化与国际化加速推进的背景下，中药配方颗粒行业正经历一场以标准化为核心的深刻变革。截至20...
长江能科迪拜孙公司完成注册 拓... 来源：新浪财经-鹰眼工作室 【财经网讯】长江三星能源科技股份有限公司（证券代码：920158，证券简...
银行职工因贪污罪获刑后留任，在... 新京报记者 刘锦涵 制作 礼牧周 ▲新京报我们视频出品（ID：wevideo） 近日，农发行福建福鼎...
黄金创40年来最大单日跌幅！金... （来源：劳动报） 转自：劳动报 1月31日，国际金银价格同步大跌，创40余年来最大跌幅。国内金饰价...
“一人公司”近来何以兴起？ 2026年开年，“一人公司”发展备受关注。这种新型创业模式正在上海、北京、江苏等地悄然兴起，凭借低成...
寒武纪预计 2025 年净利润... 消息，AI 芯片企业寒武纪今日发布 2025 年年度业绩预告： 经财务部门初步测算，公司预计 2...
和讯投顾徐剑波：ETF买入法！ 这轮牛市是机构主导的ETF牛市，选对ETF往往比选股更加赚钱。那么如何投资ETF？今天教给大家一个非...
君乐宝上市申请已递交，国内乳品... 2026年 1月19日，中国领先的综合乳制品企业君乐宝乳业集团股份有限公司正式向香港联交所递交主板上...
大涨！马斯克，突传大消息！重磅... SpaceX的“赚钱能力”曝光。 据最新消息，世界首富埃隆·马斯克旗下的商业航天公司SpaceX去年...
原创 顶... 2025年微博之夜定档于2026年2月5日北京线上直播，这场已经走过二十多年风雨的互联网年度盛典，因...
体检查出肺结节？3个日常行为正... 太原龙城中医医院科普：如今越来越多人在体检中发现肺结节，看到报告上的“阴影”便忧心忡忡。其实研究表明...
记者观察丨美联储下任主席提名揭... 在经过长达一年反复挑选后，美国总统唐纳德·特朗普终于做出决定，提名凯文·沃什为下一任美联储主席，接替...
首饰金，一夜大跌上百元！金价暴... 【导读】多家首饰品牌金价出现大幅下跌 中国基金报记者 忆山 随着国际金价急速下跌，国内首饰金价也迎来...