題目來自nyist第17題，詳細(xì)如下：

描述

輸出字符串的最長遞增子序列的長度

經(jīng)典題目，與最大和連續(xù)子串有相似之處，但是這里的子序列是可以不連續(xù)的。

DP解法，找遞推關(guān)系：設(shè)置dp數(shù)組，作為從頭到i的串中遞增序列的最大長度。比如對(duì)于序列2、4、1、5， 當(dāng)考慮到5時(shí)，前面dp數(shù)組值分別為1、2、1，對(duì)2、4、5序列，他的dp值為3，對(duì)于1、5序列，dp值為2，取最大值，3作為他的dp值，于是dp數(shù)組變?yōu)榱?、2、1、3；由于總體最大值一定是某一次計(jì)算出的值，可以設(shè)置一個(gè)全局變量max記錄dp數(shù)組的最大值，即為所求。如果當(dāng)前值比前面序列所有值都小則dp為1。

代碼如下：

#include<stdio.h>char s[10000+5];int dp[10000+5];int main(){	int T;	scanf("%d",&T);	while(T--)	{		scanf("%s",s);		int max=-1;			for(int i=0;i<strlen(s);i++)		{			dp[i]=1;			for(int j=0;j<i;j++)			{				if(s[i]>s[j] && dp[j]+1>dp[i]) //判斷是否遞增以及通過循環(huán)取其中最大值				dp[i]=dp[j]+1;			}			max = max > dp[i] ? max : dp[i];		}		PRintf("%d/n",max);	}	return 0;}經(jīng)典題目，值得反復(fù)思考。