最长不下降子序列(Onlogn算法)

作者:czp 分类: PAT 发布于:2017-1-4 13:58 ė631次浏览 60条评论
Time limit: 1000MS    Memory limit: 32768K 
Total Submit: 16    Accepted: 7 

最长不下降子序列(Onlogn算法

一个数的序列bi,当b1 <= b2 <= ... < =bS的时候,我们称这个序列是不下降的。对于给定的一个序列(a1, a2, ..., aN),我们可以得到一些不下降的子序列(ai1, ai2, ..., aiK),这里1<= i1 < i2 < ... < iK <= N。比如,对于序列(1, 7, 3, 5, 9, 4, 8),有它的一些不下降子序列,如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4,比如子序列(1, 3, 5, 8)

Input

多组cas  每组cas 两行:

第一行 输入一个数 n (n < 10000) 表示有n个数

第二行 n个数, 分别代表每个数;

Output

每个cas 一行  输出 该书数列的最长的长度 

Sample Input 

7

1 7 3 5 9 4 8

 

Sample Output

4


#include<algorithm>
#include <iostream>

using namespace std;

int *input(int n) {
    int i;
    int *array = new int[n + 1];

    for (i = 1; i <= n; i++) {
        cin >> array[i];
    }

    return array;
}

int main() {
    int n, i;
    int *array, *data;

    while (cin >> n) {
        array = input(n);
        data = new int[n + 1];

        data[1] = array[1];
        int len = 1;
        for (i = 2; i <= n; i++) {
            if (array[i] >= data[len]) {
                data[++len] = array[i];
            } else {
                unsigned long j = upper_bound(data + 1, data + len + 1, array[i]) - data;
                data[j] = array[i];
            }
        }
        cout << len << endl;
    }

    return 0;
}

本文出自 czp的装逼站,转载时请注明出处及相应链接。

0

发表评论

电子邮件地址不会被公开。必填项已用*标注


Ɣ回顶部