# 11580: 【原1580】LIS

### 题目描述

author: ZH 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1580 ﻿# Description 给一个序列，求它的最长递增子序列的长度。 如 `1 6 2 5 4 7`这些数字中，`1 2 5(4) 7` 是最长的上升子序列，长度为4.

## Sample Input

``````10
17 15 61 17 21 61 100 97 69 7
``````

## Sample Output

``````5
``````

## Limits

1. 对于30%的数据，n <= 100。
2. 对于60%的数据，n <= 1000。
3. 对于90%的数据，n <= 10000。
4. 对于100%的数据，n <= 1000000, 1 <= x[i] <= 10000000。

## ligongzzz's solution

``````#include "iostream"
using namespace std;

int myStack[1000000] = { 0 }, stackn = 0;

int main() {
ios::sync_with_stdio(false);
cin.tie(0);

int num;
cin >> num;
for (int i = 0; i < num; i++) {
int temp;
cin >> temp;

if (stackn == 0 || temp > myStack[stackn - 1])
myStack[stackn++] = temp;
else {
//二分查找
int ll = 0, rr = stackn - 1;
while (ll < rr) {
int mid = (ll + rr) >> 1;
if (myStack[mid] < temp)
ll = mid + 1;
else
rr = mid;
}
//替换
myStack[ll] = temp;
}
}

cout << stackn;

return 0;
}
``````

## Neight99's solution

``````#include <iostream>

using namespace std;

const int maxN = 1e6 + 100;

int n;
long long nums[maxN], ans[maxN] = {0};

int m(int left, int right) { return (left >= right) ? left : right; }

int LIS() {
int max = 0;

for (int k = 0; k < n; k++) {
int i = 0, j = max;
while (i != j) {
int m = (i + j) / 2;
if (ans[m] < nums[k]) {
i = m + 1;
} else {
j = m;
}
}
ans[i] = nums[k];
max = m(i + 1, max);
}

return max;
}

int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

int result;

cin >> n;
for (int i = 0; i < n; i++) {
cin >> nums[i];
}

result = LIS();

cout << result;

return 0;
}
``````

## WashSwang's solution

``````#include <iostream>
#include <cstdio>
using namespace std;
int n,st[1100000],a[1000001],top,l,r,m;
int main() {
scanf("%d",&n);
for (int i=0;i<n;++i)
scanf("%d",&a[i]);
st[0]=-1;
for (int i=0;i<n;++i){
if (a[i]>st[top]) st[++top]=a[i];
else{
l=1;
r=top;
while (l<=r){
m=(l+r)/2;
if (st[m]<=a[i]) l=m+1;
else r=m-1;
}
if (st[l-1]!=a[i]) st[l]=a[i];
}
}
printf("%d",top);
return 0;
}
``````

## yyong119's solution

``````#include <cstdio>
#include <iostream>
#define MAX_N 1000010
using namespace std;
int n, len, tmp;
int lis[MAX_N];
char ch = getchar(); int res = 0, flag = 1;
while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
if (ch == '-') flag = -1, ch = getchar();
while (ch >= '0' && ch <= '9') res = res * 10 + ch - '0', ch = getchar();
return res * flag;
}
int main() {