[LeetCode] 673. Number of Longest Increasing Subsequence

[frdmu]

Given an integer array nums, return the number of longest increasing subsequences.

Notice that the sequence has to be strictly increasing.

 

Example 1:

Input: nums = [1,3,5,4,7]
Output: 2
Explanation: The two longest increasing subsequences are [1, 3, 4, 7] and [1, 3, 5, 7].

Example 2:

Input: nums = [2,2,2,2,2]
Output: 5
Explanation: The length of longest continuous increasing subsequence is 1, and there are 5 subsequences' length is 1, so output 5.

 

Constraints:

• 1 <= nums.length <= 2000
• -106 <= nums[i] <= 106

 
解法：
类似300.求最长公共子序列的长度，这里又多了一步，求最长公共子序列的个数，所以需要再增加一个cnt[i]，表示以元素nums[i]结尾的最长公共子序列的个数。代码如下：

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n, 1), cnt(n, 0);
        if (n <= 1) return n;
        cnt[0] = 1;
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i])
                    dp[i] = max(dp[i], dp[j]+1);   
            }
            for (int j = 0; j < i; j++) {
                if (dp[j]+1 == dp[i] && nums[j] < nums[i])
                    cnt[i] += cnt[j];
            }
            cnt[i] = max(cnt[i], 1); 
        }
              
        int max = -1, res = 0;
        for (int i = 0; i < n; i++) {
            if (dp[i] > max)
                max = dp[i];
        } 
        for (int i = 0; i < n; i++) {
            if (max == dp[i])
                res += cnt[i];
        }
        
        return res;
    } 
};
/*
 nums
 dp
 cnt

   1 2 4 3 5 4 7 2    
   1 2 3 3 4 4 5 2
   1 1 1 1 2 1 3 1 
   
   2 2 2 2 2 
   1 1 1 1 1
   1 1 1 1 1
   
   1 3 5 4 7
   1 2 3 3 4
   1 1 1 1 2
*/