最长递增序列.cpp

来自「里面包含vc的经典算法,如动态规划,分治,回溯,贪心算法等」· C++ 代码 · 共 44 行

#include <iostream.h>

void Find( int a[],int b[],int c[],int n)
{
	int i ,j ,max;
	for(i  = n-2 ; i >=0 ; i --)
	{
		max=-1 ;
		for(j= i+1 ; j < n ;  j ++)
			if(a[i] < a[j]&&b[j]>max)
			{
				b[i] = b[j] + 1 ;
				max =  b[j] ;
				c[i] = j; 
			}
	}
}

int main()
{
	int a[100],b[100],c[100];
	int i,n,temp ;
	cin>>n;
	for(i = 0 ; i < n ; i ++)
	    cin>>a[i] ;
	for(i =0 ; i < n ; i ++)
	{
		b[i] = 1 ;
		c[i] =  -1 ; 
	}
	Find(a,b,c,n);
	int max = 0 ;
	for(i = 1 ; i < n ; i ++)
		if(b[max]<b[i]) max = i ;
	cout<<a[max]<<" " ;
    temp = c[max] ;
	while(temp!=-1)
	{
		cout<<a[temp]<<" " ;
        temp = c[temp] ;
	}
	cout<<endl;
	return 1;
}