0673. Number of Longest Increasing Subsequence

题目信息

题号:

0673

难度:

Medium

主题:

数组、严格递增子序列、最长长度、按下标方案计数

原题:

LeetCode 0673

重点:

子序列无需连续但保留相对顺序、递增必须严格、先确定全局最长长度、不同下标选择分别计数

题目重述

给定整数数组 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,三个单独位置各构成一种最长方案。