# C++, DP with explanation, O(n^2)

• The solution is based on DP.

``````For a sequence of numbers,
cnt[k] is total number of longest subsequence ending with nums[k];
len[k] is the length of longest subsequence ending with nums[k];
``````

Then we have following equations

``````len[k+1] = max(len[k+1], len[i]+1) for all i <= k and nums[i] < nums[k+1];
cnt[k+1] = sum(cnt[i]) for all i <= k and nums[i] < nums[k+1] and len[i] = len[k+1]-1;
``````

Starting case and default case: cnt[0] = len[0] = 1;

``````class Solution {
public:
int findNumberOfLIS(vector<int>& nums) {
int n = nums.size(), maxlen = 1, ans = 0;
vector<int> cnt(n, 1), len(n, 1);
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
if (len[j]+1 > len[i]) {
len[i] = len[j]+1;
cnt[i] = cnt[j];
}
else if (len[j]+1 == len[i])
cnt[i] += cnt[j];
}
}
maxlen = max(maxlen, len[i]);
}
// find the longest increasing subsequence of the whole sequence
// sum valid counts
for (int i = 0; i < n; i++)
if (len[i] == maxlen) ans += cnt[i];
return ans;
}
};

``````

• Thanks for sharing the elegant code!

• This post is deleted!

• @zestypanda One qq - you say in the equation:

`len[k+1] = max(len[k+1], len[i]+1)`, but you check only for `len[k+1] = max(len[k+1], len[i])` in the code. Why so?

• @zestypanda One qq - you say in the equation:

`len[k+1] = max(len[k+1], len[i]+1)`, but you check only for `len[k+1] = max(len[k+1], len[i])` in the code. Why so?

the place you mentioned in the code is for output. in the code, it is

``````if (len[j]+1 > len[i]) {
len[i] = len[j]+1;
cnt[i] = cnt[j];
}
``````

• @beetlecamera Sorry, could you please elaborate? What output do you mean?

• @BatCoder Sorry, I am not sure whether I follow your question. The equation is for DP. After DP, you get the count and length of longest sequence ending with nums[k]. However, it may not be the longest one in the whole sequence. You have to find the max value of all len[k] for k = 1...n, and sum the valid count.

• @zestypanda Small point:

The last two tasks can be done in a single for loop. You don't need two separate for loops to do that (I was asked this `small`optimization in an interview once).

``````        for(int i= 0; i<n; i++) {
if(len[i]>maxlen) {
maxlen=len[i];
ans=0;
}
if(len[i]==maxlen)
ans+=cnt[i];
}
``````

• @BatCoder Thank you! I have incorporated your suggestion.

• I am confused that why this is not right? I feel I did the same thing as you did:

``````    public int findNumberOfLIS(int[] nums) {
if(nums==null || nums.length<1){
return 0;
}
if(nums.length==1){
return 1;
}
int[] dp = new int[nums.length];
dp[0]=1;
int max = 1;
for(int i=1;i<nums.length;i++){
dp[i]=1;
for(int j=0;j<i;j++){
if(nums[i]>nums[j]){
dp[i] = Math.max(dp[i],dp[j]+1);
}
}

max = Math.max(max,dp[i]);
}
Map<Integer,Integer> map = new HashMap<>();
for(int i=0;i<nums.length;i++){
if(dp[i]==1){
map.put(1,map.getOrDefault(1,0)+1);
}else{
map.put(dp[i],map.getOrDefault(dp[i],0)+map.get(dp[i]-1));
}
}
return map.get(max);
}

``````

• @tiandiao123

map.put(dp[i],map.getOrDefault(dp[i],0)+map.get(dp[i]-1));

This line in your code is incorrect, which causes your code generate a larger number. You can't directly add map.get(dp[i]-1) there, since the last element of previous subsequence with length dp[i]-1 may not be less than nums[i], so there is not increasing sequence here. For instance, with the input [1,2,4,3,5,4,7], dp[5] = 4, however previous subsequence with length 3 [1,2,4] can't form a subsequence [1,2,4,4] with nums[5].

• @xy1994 Oh,Got it!!! You are right, thank you!!!

• @zestypanda Hello, I read your solution and I can't understand a part of it.
Could you please explain the line

``````else if (len[j]+1 == len[i])
cnt[i] += cnt[j];
``````

The way I interpret the statement is, for a value nums[j] which is greater is than nums[i], if the len[j] + 1 == len[i], increase the count at i .

I don't understand how len[i] will be greater than len[j] if nums[j] is greater than
or equal to nums[i]. Could you provide an example of such a case please ?

Thank you.

• @nightfox_lemarc len[j] is initially 1, and it is NOT the max length until the end of the loop.
For example, the numbers are

``````1, 2, 4, 6;
``````

During the loop, len[3] will change from 1 to 2, then to 3, then to 4.

• else if (len[j]+1 == len[i])
cnt[i] += cnt[j];

Could you explain these two lines? Thank you.

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