#include<cstring>
#include<iostream>
#include<stack>
#include <algorithm>
using namespace std;
int dp[100][100];
char D[100][100];
stack<char> st;
string s1,s2;
int LCS(string s1,string s2)
{
for(int i=0;i<100;i++)
{
dp[i][0] = dp[0][i] = 0;
}
for(int i=0;i<s1.length();i++)
for(int j=0;j<s2.length();j++)
{
if(s1[i] == s2[j])
{
dp[i][j] = dp[i-1][j-1]+1;
D[i][j] = ‘x‘;
}
else
{
dp[i][j] = dp[i-1][j] > dp[i][j-1]?dp[i-1][j] : dp[i][j-1];
if(dp[i-1][j] > dp[i][j-1])
{
dp[i][j] = dp[i-1][j];
D[i][j] = ‘s‘;
}
else
{
dp[i][j] = dp[i][j-1];
D[i][j] = ‘z‘;
}
}
}
int p = s1.length()-1;
int q = s2.length()-1;
while(p>=0&&q>=0)
{
if(D[p][q] == ‘z‘)
{
q--;
}
else if(D[p][q] == ‘s‘)
{
p--;
}
else if(D[p][q] == ‘x‘)
{
st.push(s1[p]);//反向输出
p--;
q--;
}
}
while(!st.empty())
{
cout<<st.top();
st.pop();
}
cout<<endl;
return dp[s1.length()-1][s2.length()-1];
}
int main()
{
//LCS
//cin>>s1>>s2;
//cout<<LCS(s1,s2)<<endl;
//LIS
cin>>s1;
s2 = s1;
sort(s2.begin(),s2.end());
cout<<LCS(s1,s2)<<endl;
return 0;
}
最长公共子序列（LCS）最长递增子序列（LIS）最长递增公共子序列（LICS）
原文：https://www.cnblogs.com/mcyushao/p/10513714.html