单调递增序列最大长度

#include "stdafx.h"
#include "iostream"
#define num 100
using namespace std;

int a[num]; //原始数据
//int c[num][num]; //最优解
int LIS(int n)
{
	int b[num]={0}; //最大长度数组
	int i,j;
	b[1]=1;
	int max=0;
	for(i=2;i<=n;i++)
	{
		int k=0; //暂存i之前的最大长度
		for(j=1;j<i;j++)
		{
			if(a[j]<=a[i]&&k<b[j])
			{
				k=b[j];
			}
		}
		b[i]=k+1;
		if(max<b[i])
			max=b[i];
	}
	return max;
}


int _tmain(int argc, _TCHAR* argv[])
{
	a[1]=65;a[2]=158;a[3]=170;a[4]=155;a[5]=239;a[6]=300;a[7]=207;a[8]=389;
	cout<<"单调递增序列最大长度："<<LIS(8)<<endl;
	system("pause");
	return 0;
}