最长上升子序列(LIS DP)

状态：d[i]表示以i结尾的最长上升子序列

状态转移：d(i) =max{0,d(j)|j<i,Aj<Ai}+1;

当A[i]>A[j]说明又多了个子序列+1; 

const int maxn=1000+5;
int main()
{int n,s[maxn],d[maxn]={0};scanf("%d",&n);for(int i=0;i<n;i++)cin>>s[i];d[0]=1;for(int i=0;i<n;i++)for(int j=0;j<i;j++)if(s[i]>s[j]) d[i]=max(d[i],d[j]+1);/*	for(int i=0;i<n;i++) cout<<d[i]<<' ';cout<<endl;  
*/	cout<<*max_element(d,d+n)<<endl;}