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.
Approach #1: C++. [DFS]
class Solution {
public:
int findNumberOfLIS(vector<int>& nums) {
int n = nums.size();
if (n == 0) return 0;
c_ = vector<int>(n, 0);
l_ = vector<int>(n, 0);
int max_len = 0;
for (int i = 0; i < n; ++i)
max_len = max(max_len, len(nums, i));
int ans = 0;
for (int i = 0; i < n; ++i)
if (len(nums, i) == max_len)
ans += count(nums, i);
return ans;
}
private:
vector<int> c_;
vector<int> l_;
// find the total number of increasing subsequence from i to n of the index.
int count(const vector<int>& nums, int n) {
if (n == 0) return 1;
if (c_[n] > 0) return c_[n];
int total_count = 0;
int l = len(nums, n);
// find the number of increasing subsequence which is short than current subsquence.
for (int i = 0; i < n; ++i)
if (nums[n] > nums[i] && len(nums, i) == l-1)
total_count += count(nums, i);
if (total_count == 0)
total_count = 1;
return c_[n] = total_count;
}
// find the max length of increasing subsequence from i to n of the index.
int len(const vector<int>& nums, int n) {
if (n == 0) return 1;
if (l_[n] > 0) return l_[n];
int max_len = 1;
for (int i = 0; i < n; ++i)
if (nums[n] > nums[i])
max_len = max(max_len, len(nums, i) + 1);
return l_[n] = max_len;
}
};
Appraoch #2: Interation. [Java]
class Solution {
public int findNumberOfLIS(int[] nums) {
int n = nums.length;
if (n == 0) return 0;
int[] c = new int[n];
int[] l = new int[n];
Arrays.fill(c, 1);
Arrays.fill(l, 1);
for (int i = 1; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (nums[i] > nums[j])
if (l[j] + 1 > l[i]) {
l[i] = l[j] + 1;
c[i] = c[j];
} else if (l[j] + 1 == l[i]){
c[i] += c[j];
}
}
}
int max_len = 0;
for (int i = 0; i < n; ++i)
if (l[i] > max_len)
max_len = l[i];
int ans = 0;
for (int i = 0; i < n; ++i) {
if (l[i] == max_len)
ans += c[i];
}
return ans;
}
}
Analysis:
The idea is to use two arrays l[n] ans c[n] to record the maximum length os Incresing Subsequence ans the coresponding number of there sequence which ends with nums[i], respectively. That is:
l[i]: the lenght of the Longest Increasing Subseuqence which ends with nums[i].
c[i]: the number of the Longest Increasing Subsequence which ends with nums[i].
Then, the result is the sum of each c[i] while its corresponding l[i] is the maximum length.
Reference: