最长递增子序列个数c++
发布时间
阅读量：
阅读量
之前曾做过的计算最长增长子序列的题目；但对其数目边界处理显得有些复杂
主要注意相等的情况要单独处理
class Solution {
public:
int findNumberOfLIS(vector<int>& nums) {
//l[i]保存以nums[i]为结尾的子序列长度，k[i]保存子序列个数
int*l=new int[nums.size()],*k=new int[nums.size()];
int lmax=1,kmax=1;
l[0]=1;k[0]=1;
for(int i=1;i<nums.size();i++){
l[i]=0;k[i]=0;
for(int j=i-1;j>=0;j--){
//寻找nums[j]<nums[i]的最长子序列[j,i)
if(nums[i]>nums[j]){
if(l[i]==l[j]){
//存在多个长度为l[j]的子序列，且每个子序列有k[j]种构造方式
k[i]+=k[j];
}
//l[j]为当前最长子序列
else if(l[i]<l[j]){
l[i]=l[j];
k[i]=k[j];
}
}
else if(nums[i]==nums[j]){
//以[j,i)间节点为结尾的序列长度小于以[0,j]为结尾的序列
if(l[i]<l[j]-1){
l[i]=l[j]-1;
k[i]=k[j];
}
else if(l[i]==l[j]-1){
k[i]+=k[j];
}
//j之前的在计算l[j]时已经搜寻过了，这里直接返回
break;
}
}
k[i]=1>k[i]?1:k[i];
//加上尾部节点i
l[i]++;
if(l[i]>lmax){
lmax=l[i];
kmax=k[i];
}
//存在多个长度为l[i]的子序列
else if(l[i]==lmax){
kmax+=k[i];
}
}
return kmax;
}
};全部评论 (0)
还没有任何评论哟~