思路
在给定的输入中寻找最优可能，可以通过动态规划实现。需要在一个未排序的序列中找到满足要求的最长序列，并输出最长序列长度。可以根据样例逐个值推导，发现每引入一个新的值时，最长序列的长度就可能+1，得到关系状态方程。
实现
1.输入：使用vector存放整数型的不定长数组，按照题目要求实现输入有点麻烦了。使用string将输入作为字符直接使用会更方便。
2.输出：dp数组存放的是各值作为新序列的最后一个值时序列的最大长度，因此需要对他们进行排序，找到最大的序列长度。
3.动态规划：外层的循环将原序列的每一个值进行遍历，内层的循环通过判断当前值和前面值的关系找到最长可能。判断的条件包括：当前值大于前面值，当前值具有的最大长度是目前最大的。
代码
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> a;
int main()
{
int i=0;
do{
cin>>i;
a.push_back(i);
}while(getchar()!='\n'); //输入
int len=a.size();
int dp[len];
for(int i=0;i<len;i++) //dp[i]=(max+1(a[j]<a[i]&&dp[j]>max))
{
int max=0;
for(int j=i;j>=0;j--)
if(a[i]>a[j]&&dp[j]>max)
max=dp[j];
dp[i]=max+1;
}
sort(dp,dp+len);
cout<<dp[len-1]; //输出
}
总结
不仅是输入数字并按照大小排序时可使用这种方法，输入字母并按照字母顺序排序也可以使用。处理动态规划类题目时重要的一步是找到关系状态方程，确定状态方程后再想循环哪一个变量、循环中是否有判断条件、怎样实现等问题。
在理解之后这道题显得比较容易，但如果没有答案参考直接使用动态规划做的话会纠结很久。再做些动态规划的题目，让这个过程变熟悉些。
