2014
03-01

# 最长上升子序列长度(LIS)-O(nlogn)算法

#include <iostream>
#define SIZE 1001

using namespace std;

int main()
{
int i, j, n, top, temp;
int stack[SIZE];
cin >> n;

top = 0;
/* 第一个元素可能为0 */
stack[0] = -1;
for (i = 0; i < n; i++)
{
cin >> temp;
/* 比栈顶元素大数就入栈 */
if (temp > stack[top])
{
stack[++top] = temp;
}
else
{
int low = 1, high = top;
int mid;
/* 二分检索栈中比temp大的第一个数 */
while(low <= high)
{
mid = (low + high) / 2;
if (temp > stack[mid])
{
low = mid + 1;
}
else
{
high = mid - 1;
}
}
/* 用temp替换 */
stack[low] = temp;
}
}

/* 最长序列数就是栈的大小 */
cout << top << endl;

//system("pause");
return 0;
}

lower_bound 函数

#include<stdio.h>
#include<string.h>
#include<algorithm>

using namespace std;

int num[10]={3,6,3,2,4,6,7,5,4,3};

const int INF=0x3f3f3f3f;
int l=10;
int g[100];
int d[100];
int main()
{
fill(g,g+l,INF);
int max_=-1;
for(int i=0;i<l;i++)
{
int j=lower_bound(g,g+l,num[i])-g;
d[i]=j+1;
if(max_<d[i])
max_=d[i];
g[j]=num[i];
}
printf("%d\n",max_);
return 0;
}

http://www.slyar.com/blog/longest-ordered-subsequence.html

1. #include <cstdio>

int main() {