liss.cpp

时间复杂度为O(nlogn)的最长单调递增子序列问题的计算程序。不是动态规划算法。在一分钟之内可以计算n=10^6个元素的递增子序列。

#pragma warning(disable: 4786)
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <time.h>
#include <set>
using namespace std;
class Node
{
public:
	int x;
	Node *next;
};

class Element
{
public:
	int key; //the key for dictionary 
	Node *head, *tail;
	int x;
	Node(int a) { x = a; next = 0;}
};

template <class T>
class LessThan
{
public:
	bool operator()(T a, T b) const {return a.key <= b.key;}
};

main()
{
	int n, x;
	char filename[128];
	FILE *file;
	int i;
	Element ele;
	set<Element, LessThan<Element> > s;

	printf("需要随机产生一个序列文件吗？(Y/N)");
	char answer;
	scanf("%c", &answer);
	if(answer=='y' || answer=='Y')
	{
		printf("要生成的序列文件名:");
		scanf("%s", filename);
		file = fopen(filename, "w");
		printf("要产生的元素个数:");
		scanf("%d", &n);
		fprintf(file, "%d\n", n);
		srand( (unsigned)time(NULL));
		for(i=0; i<n; i++)
		{
			fprintf(file, "%d ", int(1.0*rand()/RAND_MAX*n+0.5));
		}
		fclose(file);
	}

	printf("\n将计算的序列文件名:");
	scanf("%s", filename);
	if((file=fopen(filename, "r"))==NULL)
	{
		printf("Error: the graph file does not exist.\n");
		return 1;
	}
time_t t_start = time(NULL);
	fscanf(file, "%d", &n);
	printf("序列元素个数:%d\n", n);
	for(i=0; i<n; i++)
	{
		fscanf(file, "%d", &x);

		ele.key = x;
		
		if(i==0)
		{
			s.insert(ele);
			s.begin()->head = s.begin()->tail = new Node(x);
			//(s.begin()->keys).push_back(x);
			continue;
		}
		set<Element, LessThan<Element> >::iterator upper;
		upper = s.upper_bound(ele);
		if(upper!=s.end())
		{
			upper->key = x;
			upper->tail->next = new Node(x);
			upper->tail = upper->tail->next;
			//upper->keys.push_back(x);
		}
		else
		{
			s.insert(s.end(), ele);
			s.rbegin()->head = s.rbegin()->tail = new Node(x);
			//(s.rbegin()->keys).push_back(x);
		}
	}
	fclose(file);
	
	printf("\n");
	printf("\n最长单调递增子序列是:");

	s.rbegin()->x = s.rbegin()->key;
	int lastkey = s.rbegin()->key;
	set<Element, LessThan<Element> >::reverse_iterator p = s.rbegin();
	p++;
	for(; p!=s.rend(); p++)
	{
		for(Node *q = p->head; q!=0; q=q->next)
		{
			if(q->x < lastkey)
				break;
		}
		p->x = q->x;
		lastkey = q->x;
		//for(list<int>::iterator q = p->keys.begin(); q!=p->keys.end(); q++)
		//{
		//	if(*q < lastkey)
		//		break;
		//}
		//p->x = *q;
		//lastkey = *q;
	}

	set<Element, LessThan<Element> >::iterator pp;
	for(pp=s.begin(); pp!=s.end(); pp++)
		printf("%d ", pp->x);
	
	printf("\n最长单调递增子序列的长度是: %d", s.size()); 
    printf("\n花费的计算时间为：%g(s)", difftime(time(NULL), t_start));
	_getch();
	return 1;
}