# [673. Number of Longest Increasing Subsequence] C++ AC Time: O(n^2), Space: O(n)

• Is it real DP problem???

Two vectors:
vector 1: store the longest length from the start to current position
vector 1: store the number of longest length from start to current position

``````class Solution {
public:
int findNumberOfLIS(vector<int>& nums) {
if(nums.empty()) return 0;
vector<int> dp_len(nums.size(), 1);
vector<int> dp_cnt(nums.size(), 1);
int res_len = 1;
int res_cnt = 1;
for(int i = 1; i < nums.size(); ++i){
int j = i-1;
int temp_len = 1;
int temp_cnt = 1;
while(j >= 0){
if(nums[j] < nums[i]){
int new_len = dp_len[j] + 1;
if(temp_len < new_len){
temp_len = new_len;
temp_cnt = dp_cnt[j];
}else if(temp_len == new_len){
temp_cnt += dp_cnt[j];
}
}
j--;
}
dp_len[i] = temp_len;
dp_cnt[i] = temp_cnt;
if(dp_len[i] > res_len){
res_len = dp_len[i];
res_cnt = dp_cnt[i];
}else if(dp_len[i] == res_len){
res_cnt += dp_cnt[i];
}
}
return res_cnt;
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.