【u023】最长上升子序列(sequence)

Time Limit: 1 second

Memory Limit: 128 MB

【问题描述】

非常经典的问题，拿来给大家练手了。序列 { 1,2,...,n } 的一个子序列是指序列 { i1, i2, ……, ik },其中 1<=i1 < i2 < …… < ik<=n, 序列 { a1, a2, ……, an } 的一个子序列是指序列 { ai1, ai2, ……, aik },其中 { i1, i2, ……, ik } 是 { 1, 2, ……, n } 的一个子序列.同时,称 k 为此子序列的长度. 如果 { ai1, ai2, ……, aik } 满足 ai1 ≤ ai2 ≤ …… ≤
aik,则称之为上升子序列.如果不等号都是严格成立的,则称之为严格上升子序列.同理,如果前面不等关系全部取相反方向,则称之为下降子序列和严格下降子序列. 长度最长的上升子序列称为最长上升子序列.本问题对于给定的整数序列,请求出其最长上升子序列的长度.

【输入格式】

第一行给出一个数字N,N < = 5000，表示给定数列的长度。第二行有N个整数，表示数列中的元素

【输出格式】

输出K的极大值，即最长上升子序列的长度

【数据规模】

Sample Input1

5

9 3 6 2 7

Sample Output1

【样例说明】

最长上升子序列为3,6,7

【题解】

程序1，用f[i]表示以i作为最后一个元素的最长上升子序列长度,f[i] = max(f[i],f[j]+1)，其中 a[i] >= a[j]; j ∈（1，i-1);

程序2,用f[i]表示长度为i的最长上升子序列的最后一个元素的最小值,在扫描输入的数组a时，如果a[i] > f[maxl]，那么maxl++,f[maxl] = a[i]，否则从maxl-1 到 1扫描一下，

找到最大的j使得a[j] <= a[i] ，然后 f[j+1] = a[i];即更新长度为j+1的最长上升子序列的最后一个数的最小值。最后输出maxl就好。

程序2可以用二分查找来优化做到nlogn,但是二分查找写起来很麻烦、

【程序1】

#include <cstdio>

int n,a[5002],f[5002],ans = 0;

void input_data()

{

    scanf("%d",&n);

    for (int i = 1;i <= n;i++)

        scanf("%d",&a[i]);

}

int ma_x( int a,int b)

{

    if (a > b)

        return a;

            else

                return b;

}

void get_ans()

{

    for (int i = 1;i <= n;i++)

        {

            f[i] = 1;//f[i] == 1表示 从这个数字开始新的一个序列 长度为1

            for (int j = 1;j <= i-1;j++) //或者从之前的序列中更新，让这个数字作为最后一个数

                {

                    if (a[i] >= a[j]) //前提是这个数字要比前面的数字大 且长度加上1之后会比这个数字作为其他序列的最后一个数字来的更好(长度更长)

                        f[i] = ma_x(f[i],f[j] + 1);

                }

            if (f[i] > ans) // 如果比最优解更优 则更新

                ans = f[i];

        }

}

void output_ans()

{

    printf("%d\n",ans);

}

int main()

{

    input_data();

    get_ans();

    output_ans();

    return 0;

}

【程序2】

#include <cstdio>

int n,a[5002],f[5002],ans = 0,maxl = 0;

void input_data()

{

    scanf("%d",&n);

    for (int i = 1;i <= n;i++)

        scanf("%d",&a[i]);

    for (int i = 1;i <= n;i++)

        f[i] = 0;

    f[0] = -200000000;//这个f[0]的边界 可以方便后面的求解

}

void get_ans()

{

    for (int i = 1;i <= n;i++)

        {

            if (a[i] >= f[maxl]) //如果比最长长度的序列的最后一个数字大 就可以更新长度了，这样是最优的

                {

                    maxl++;

                    f[maxl] = a[i];

                } //没有办法更新最大长度 就在前面的数字中找，更新一下最后一个数字的最小值

                    else

                        for (int j = maxl-1; j >=0; j--) //从大到小更新这样保证是最大的j

                            if (f[j] <= a[i])

                                {

                                    f[j+1] = a[i];

                                    break;

                                }

        }

}

void output_ans()

{

    printf("%d\n",maxl);

}

int main()

{

    //freopen("F:\\rush.txt","r",stdin);

    input_data();

    get_ans();

    output_ans();

    return 0;

}

巴特西