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.

Input Format

第一行有三个整数n ，代表序列的长度。

接下来一行 n 个正整数代表序列x[1], x[2]……, x[n]。

Output Format

输出最长递增子序列的长度。

注意：答案没有对任何数取模。

Sample Input

10
17 15 61 17 21 61 100 97 69 7

Sample Output

Limits

对于30%的数据，n <= 100。
对于60%的数据，n <= 1000。
对于90%的数据，n <= 10000。
对于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];
inline int read() {
    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() {
    n = read(); tmp = read(); lis[++len] = tmp;
    for (register int i = 1; i < n; ++i) {
        tmp = read();
        if (tmp > lis[len]) lis[++len] = tmp;
        else {
            int pos = lower_bound(lis, lis + len, tmp) - lis;
            lis[pos] = tmp;
        }
    }
    printf("%d", len);
    return 0;
}