題目來自nyist第17題，詳細如下：

描述

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

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

DP解法，找遞推關系：設置dp數組，作為從頭到i的串中遞增序列的最大長度。比如對于序列2、4、1、5， 當考慮到5時，前面dp數組值分別為1、2、1，對2、4、5序列，他的dp值為3，對于1、5序列，dp值為2，取最大值，3作為他的dp值，于是dp數組變為了1、2、1、3；由于總體最大值一定是某一次計算出的值，可以設置一個全局變量max記錄dp數組的最大值，即為所求。如果當前值比前面序列所有值都小則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]) //判斷是否遞增以及通過循環取其中最大值				dp[i]=dp[j]+1;			}			max = max > dp[i] ? max : dp[i];		}		PRintf("%d/n",max);	}	return 0;}經典題目，值得反復思考。