【DP入门】单调递增最长子序列

题目来自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;}经典题目，值得反复思考。