最长不下降子序列.cpp

求一个字符串的最长不下降子序列

// 最长不下降子序列.cpp : Defines the entry point for the console application.
/*
MaxLen (k)表示以ak做为“终点”的最长上升子序列的长度
MaxLen (k) = Max { MaxLen (i)：1<i < k 且ai < ak且k≠1 } + 1
*/
//

#include "stdafx.h"
#include <stdio.h>
#include <memory.h>
#define MAX_N 1000
int b[MAX_N +10];
int aMaxLen[MAX_N +10];
main(){
	int N;
	scanf("%d", &N);
	for( int i=1;i<=N;i++ )
		scanf("%d", &b[i]);
	aMaxLen[1] = 1;    //以1为终点的最长上升子序列的长度为1
	for( i = 2; i <= N; i++ ) 
	{
	//每次求以第i个数为终点的最长上升子序列的长度
	int nTmp = 0; //记录满足条件的，第i个数左边的上升子序列的最大长度
	for( int j = 1; j < i; j ++ ) 
	{ //察看以第j个数为终点的最长上升子序列
	if( b[i] > b[j] ) {
	if( nTmp < aMaxLen[j] )
	nTmp = aMaxLen[j];}
	}
	aMaxLen[i] = nTmp + 1;}
	int nMax = -1;
	for( i = 1; i <= N; i ++ )
	if( nMax < aMaxLen[i])
	nMax = aMaxLen[i];
	printf("%d\n", nMax);
	return 0;
}