单调递增最长子序列

#include<iostream>
#include<string.h>
#include<memory.h>
using namespace std;
int main()
{
	int num;
	cin>>num;
	while(num--)
	{
		char str[10001];
		int size,dp[10001];
		cin>>str;
		size=strlen(str);   //输入的字符串长度不包括‘\0‘
		memset(dp,0,sizeof(dp)); //数组赋值全部为0，赋值为1会出错，应为memset是按照字节赋值
		for(int i=0;i<size;i++)
		{

			for(int j=0;j<i;j++)


			if(str[i]>str[j]&&(dp[j]+1>dp[i]))  //判断单调，同时更新dp值，i位置可以形成多个子序列，找最长的那个
			dp[i]=dp[j]+1;

		}

		int result=0;    
		for(int i=0;i<size;i++)
		{
			if(dp[i]>result)
				result=dp[i];
		}
		cout<<result+1<<endl;  //开始赋值都为0所以要增加1


	}

}

 例程：

 
#include<iostream>
#include <string>
//#include <time.h>
using namespace std;
int main()
{
	//freopen("1.txt","r",stdin);
	int n ;
	cin>>n;
	while(n--)
	{
		string str;
		int count=1;
		cin>>str;
		int a[200];
		a[0]=-999;
		for (int i=0;i<str.length();i++)
		{

			for (int j=count-1;j>=0;j--)
			{
				if((int)str[i]>a[j])
				{
					a[j+1]=str[i];
					if(j+1==count) count++;
					break;
				}
			}
		}
		cout<<count-1<<endl;
	}
	//cout<<(double)clock()/CLOCKS_PER_SEC<<endl;
	return 0;
}        

单调递增最长子序列,布布扣,bubuko.com

单调递增最长子序列

原文：http://blog.csdn.net/u012134276/article/details/23424795