最长递增子序列的个数

问题描述

给定一个未排序的整数数组，找到最长递增子序列的个数。

示例 1:

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

来源：LeetCode

解法一

计算LIS的个数，LIS的解法在这里。因为最长递推子序列的个数是不同的，分两种情况：1.LIS[i]是最大的LIS，但以i结尾的LIS个数有多个，在遍历的过程中，逐渐把刚好等于最大长度-1的，都加和起来，作为LIS[i]的序列个数；2.不同结尾的LIS可能都是最大值，则需要把这些也加和，作为最终的结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int n = nums.size();
        if(n <= 1) return n;
        vector<int> dp(n, 1);    // 以j结尾的最大递增子序列的长度
        vector<int> count(n, 1); // 以j结尾的最大递增子序列的个数
        int max_len = 1;
        for(int i = 1; i < n; i++) {
            for(int j = 0; j < i; j++) {
                // 找到相同最大长度的加和起来
                // 这里如何判断最大长度？有更大的值赋值替换即可
                if(nums[j] < nums[i]) {
                    if(dp[j] >= dp[i]) { // 赋值更新 长度采用j的长度
                        dp[i] = dp[j] + 1;
                        count[i] = count[j];
                    } else if(dp[j] + 1 == dp[i]) { // 当前长度下刚好相等
                        count[i] += count[j];
                    }
                }
            }
            max_len = max(max_len, dp[i]);
        }
        int cnt = 0;
        for(int i = 0; i < n; i++) {
            if(max_len == dp[i]) {
                cnt += count[i];
            }
        }
        return cnt;
    }
};