assigntwo.cpp

求任意长度数据的最长有序子序列的动态规划算法实现！

// AssignTwo.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#define SIZE 55

int _tmain(int argc, _TCHAR* argv[])
{
	int  a[]={9,44,32,12,7,42,34,92,35,
		37,41,8,20,27,83,64,61,28,39,93,29,17,
		13,14,55,21,66,72,23,73,99,1,2,88,77,3,
		65,83,84,62,5,11,74,68,76,78,67,75,69,70,22,71,24,25,26};
	int b[SIZE]={0};
	int c[SIZE]={0};
	int i,j,k,m,p,q=0,s,t;
	//clrscr();
	for (i=SIZE-1;i>0;i--)
	{
		for(j=i-1;j<SIZE-1;j++)
		{
			if(a[i-1]<a[j+1]) 
			{
				if(b[i-1]<=b[j+1])
				{
					b[i-1]=b[j+1]+1;
					c[i-1]=j+1;
				}
			}
		}
	}
	for(k=0;k<=SIZE-1;k++)
	{
		printf("%d  ",b[k]);
	}
	printf("\n");
	for(m=0;m<=SIZE-1;m++)
	{ 
		printf("%d  ",c[m]);
	}
	printf("\n");
	p=b[0];
	for(s=1;s<SIZE-1;s++)
	{	
		if(b[s]>p)
		{
			p=b[s];
			q=s;
		}
	}
	printf("%d  %d\n",p,q);
	for (t=q;c[t]!=0;t=c[t])
	{
		printf("%d ",a[t]);
	}
	return 0;
}