Skip to content

Latest commit

 

History

History
 
 

673. Number of Longest Increasing Subsequence

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 

Given an unsorted array of integers, find the number of longest increasing subsequence.

Example 1:

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

Example 2:

Input: [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.

Note: Length of the given array will be not exceed 2000 and the answer is guaranteed to be fit in 32-bit signed int.

Related Topics:
Dynamic Programming

Similar Questions:

Solution 1. DP

Consider the subproblem in range A[0..i] and the LIS must ends with A[i].

Let len[i] be the length of longest LIS ending with A[i].

Let cnt[i] be the count of longest LIS ending with A[i].

len[i] = 1 + max( len[j] | 0 <= j < i && A[j] < A[i] )
cnt[i] = sum( cnt[j] | 0 <= j < i && len[j] + 1 == len[i] )

The answer is

sum( cnt[i] | len[i] == maxLen )
    where maxLen = max( len[i] | 0 <= i < N )
// OJ: https://leetcode.com/problems/number-of-longest-increasing-subsequence/
// Author: github.com/lzl124631x
// Time: O(N^2)
// Space: O(N)
class Solution {
public:
    int findNumberOfLIS(vector<int>& A) {
        if (A.empty()) return 0;
        int N = A.size(), ans = 0, maxLen = 0;
        vector<int> len(N, 1), cnt(N, 1);
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < i; ++j) {
                if (A[j] >= A[i]) continue;
                if (len[i] < 1 + len[j]) len[i] = 1 + len[j], cnt[i] = cnt[j];
                else if (len[i] == 1 + len[j]) cnt[i] += cnt[j];
            }
            if (len[i] > maxLen) maxLen = len[i], ans = cnt[i];
            else if (len[i] == maxLen) ans += cnt[i];
        }
        return ans;
    }
};