最长递增子序列的个数 图解题解

673 到底在数什么

给整数数组 nums，在它所有严格递增的子序列里挑最长的，问有几条。子序列可跳着挑但保持原顺序，严格递增指后一个比前一个大。以 nums=[1,2,4,3,5,7,6,8] 为例，最长长度 6，凑出它的走法有 4 条，答案就是 4。

普通 LIS 只算长度，个数从哪来

普通最长递增子序列（LIS）用一维动态规划：len[i] 表示以下标 i 结尾的最长上升子序列长度，往前找所有比 nums[i] 小的 nums[j]，取 len[i]=max(len[j]+1)。只答多长、不答条数。

于是再开 cnt 数组，cnt[i] 记：以 i 结尾、长度恰等于 len[i] 的子序列有几条。cnt 全初始化为 1，每个数自成长度 1 的子序列。

cnt 更新为什么分「重置」和「累加」两种

递推 cnt[i] 时，每遇到能接的 nums[j]（nums[j] 小于 nums[i]），看 len[j]+1 与 len[i] 谁大，这一步是重置还是累加，全看它。

len[j]+1 大于 len[i]：经 j 接出更长的子序列，原先较短方案作废。于是 len[i]=len[j]+1，cnt[i] 改写成 cnt[j]——是覆盖不是累加，新长度的条数只由 j 提供。

len[j]+1 等于 len[i]：经 j 接出的长度与已记最长相等，于是 cnt[i]+=cnt[j]。一句话：更长重置、等长累加。len[j]+1 小于 len[i] 更短，跳过。

拿 [1,2,4,3,5,7,6,8] 亲手算一遍

下标 0 到 7。前几格顺推：起手 len、cnt 都是 1；2 接 1，len=2、cnt=1；4 接 2，len=3、cnt=1；3 接 2，len=3、cnt=1。这几步都是长度加一、cnt 继承 1，还没碰上抉择。

下标 4 的数 5 最能看清两种更新。接 4（len=3）得 len[4]=4，cnt[4] 先改写成 cnt[2]=1；再接 3（len 也 3）也得 4，与 len[4] 相等，累加 cnt[4]+=cnt[3]=1，得 cnt[4]=2。

往后：7 接 5，len=5、cnt=2；6 接 5，len=5、cnt=2。8 接 7、6（都 len=5）得 len=6：先由 7 定 len[7]=6、cnt[7]=2，再遇等长的 6 累加 cnt[7]+=cnt[6]=2，得 cnt[7]=4。填完 len=[1,2,3,3,4,5,5,6]、cnt=[1,1,1,1,2,2,2,4]。

答案为什么要把多个 cnt 加起来

最长长度是 len 的最大值 6，本例只在下标 7，把该处 cnt 相加即答案 4。之所以相加：最长子序列可在不同位置结尾，凡 len[i] 等于最大值的下标都要计入 cnt；数据一变常散几处，只读末格就漏。

复杂度：外层每个 i、内层往前扫 j，O(n²)；只用 len、cnt 两个数组，空间 O(n)。两处最容易写反：更长时把 cnt[i]=cnt[j] 误写成 +=，混入作废方案；只返回末格 cnt，漏掉别处的结尾。

Python

def findNumberOfLIS(nums):
    n = len(nums)
    length = [1] * n
    count = [1] * n
    for i in range(n):
        for j in range(i):
            if nums[j] < nums[i]:
                if length[j] + 1 > length[i]:
                    length[i] = length[j] + 1
                    count[i] = count[j]
                elif length[j] + 1 == length[i]:
                    count[i] += count[j]
    mx = max(length)
    return sum(c for l, c in zip(length, count) if l == mx)

C++

int findNumberOfLIS(vector<int>& nums){
    int n = nums.size();
    vector<int> len(n, 1), cnt(n, 1);
    int mx = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < i; j++) if(nums[j] < nums[i]){
            if(len[j] + 1 > len[i]){ len[i] = len[j] + 1; cnt[i] = cnt[j]; }
            else if(len[j] + 1 == len[i]) cnt[i] += cnt[j];
        }
        mx = max(mx, len[i]);
    }
    int ans = 0;
    for(int i = 0; i < n; i++) if(len[i] == mx) ans += cnt[i];
    return ans;
}

Java

int findNumberOfLIS(int[] nums){
    int n = nums.length, mx = 0, ans = 0;
    int[] len = new int[n], cnt = new int[n];
    for(int i = 0; i < n; i++){
        len[i] = 1; cnt[i] = 1;
        for(int j = 0; j < i; j++) if(nums[j] < nums[i]){
            if(len[j] + 1 > len[i]){ len[i] = len[j] + 1; cnt[i] = cnt[j]; }
            else if(len[j] + 1 == len[i]) cnt[i] += cnt[j];
        }
        mx = Math.max(mx, len[i]);
    }
    for(int i = 0; i < n; i++) if(len[i] == mx) ans += cnt[i];
    return ans;
}