最长上升子序列nlogn算法

最长上升子序列nlogn算法

题目描述:

给定一个整型数组, 求这个数组的最长严格递增子序列的长度。 譬如序列1 2 2 4 3 的最长严格递增子序列为1,2,4或1,2,3.他们的长度为3。

输入:

输入可能包含多个测试案例。
对于每个测试案例,输入的第一行为一个整数n(1<=n<=100000):代表将要输入的序列长度
输入的第二行包括n个整数,代表这个数组中的数字。整数均在int范围内。

输出:

对于每个测试案例,输出其最长严格递增子序列长度。

样例输入:
4
4 2 1 3
5
1 1 1 1 1
样例输出:
2
1
AC代码:
#include<stdio.h>
#include<string.h>

#define MAX 100000

int main(void)
{
	int n,top;
	int num[MAX],Stack[MAX];
	int low,mid,high;
	int i;
	while(scanf("%d",&n)!=EOF)
	{
		top=0;
		memset(Stack,0,sizeof(Stack));
		for(i=0;i<n;i++)
			scanf("%d",&num[i]);
		Stack[top]=-0xFFFFFF;
		for(i=0;i<n;i++)
		{
			if(num[i]>Stack[top])
				Stack[++top]=num[i];
			else
			{
				low=1;
				high=top;
				while(low<=high)
				{
					mid=(low+high)/2;
					if(num[i]>Stack[mid])
						low=mid+1;
					else
						high=mid-1;
				}
				Stack[low]=num[i];
			}
		}
		printf("%d\n",top);
	}

	return 0;
}

原理:栈中的数字越小,子串越长的可能性越大。。。

最长上升子序列nlogn算法

上一篇:编写更加稳定、可读性强的JavaScript代码


下一篇:firefox 插件开发