最长上升子序列(最长递增子序列,LIS)

最长上升子序列(最长递增子序列,LIS)

朴素dp(O($n^2$))

• 状态表示：
  • 集合$dp[]$：所有满足上升条件的元素集
  • 属性：cnt，$dp[i]$表示以i结尾的上升子序列长度，$init(dp[])=1$
• 状态计算：
  • $i$为当前工作区间尾指针,$j$为当前工作区间工作指针
  • 不选$i:a[j]>a[i]$，无法满足最优解，不选
  • 选$i:a[j]<a[i$],满足上升条件,可选。$dp[i]$的结果转移自$dp[j]$，因此转移方程为$dp[i]=max(dp[i],dp[j]+1)$。当$dp[i]=dp[j]+1$时，说明$a[i]$已选，否则证明$a[j]$包含在之前已选的子集中

extern vector<int>v(n),dp(n,1);
int lis(){
	for(int i=0;i<n;i++)
        for(int j=0;j<i;j++)
            if(v[j]<v[i])//选v[i]
                dp[i]=max(dp[i],dp[j]+1);
    return *max_element(dp.begin(),dp.end());
}

LCS求解LIS(O($n^2$))

思路：将序列排序，两序列的LCS即为原序列的LIS

贪心(O($n\log n$))

思路：设原序列$v[]$，答案序列$ans[]$，当前工作指针为$i$。初始化$ans[0]=v[0]$，遍历原序列$v[]$：

• 若$v[i]$>$ans[ans.size()-1]$，则将$v[i]$加入$ans[]$末尾
• 否则，用$v[i]$替换$ans[]$中首个$\ge v[i]$的元素。由于$ans[]$始终有序，故可采用二分加速

extern int n;
extern vector<int>v,ans;
void lis(){
    ans.push_back(v[0]);
    for(auto i:v){
        if(i>ans[ans.size()-1]) ans.push_back(i);
        else ans[distance(ans.begin(),lower_bound(ans.begin(),ans.end(),i))]=i;
    }
    cout<<ans.size()<<endl;
}