0673. Number of Longest Increasing Subsequence¶
题目信息¶
- 题号:
0673
- 难度:
Medium
- 主题:
数组、严格递增子序列、最长长度、按下标方案计数
- 原题:
- 重点:
子序列无需连续但保留相对顺序、递增必须严格、先确定全局最长长度、不同下标选择分别计数
题目重述¶
给定整数数组 nums,在所有严格递增子序列中找出最大长度,并返回具有这一最大长度的子序列数量。
子序列可以删除任意元素但不能改变剩余元素的相对顺序;相邻选中值必须严格增加,相等不算递增。即使两个子序列的数值序列相同,只要使用的数组下标不同,也视为不同方案。nums.length 位于 [1, 2000],元素值位于 [-10^6, 10^6],答案保证在 32 位有符号整数范围内。
自建示例¶
最长子序列由不同下标组合产生:
输入:nums = [2,1,3,2,4]
输出:3
解释:最长长度为 3,对应 [2,3,4]、[1,3,4] 和 [1,2,4] 三种下标选择。
所有元素相等:
输入:nums = [6,6,6]
输出:3
解释:严格递增子序列的最大长度只能是 1,三个单独位置各构成一种最长方案。