2019蓝桥训练模拟填空——LIS 最长上升子序列

计蒜客蓝桥模拟

LIS 是最长上升子序列。什么是最长上升子序列？ 就是给你一个序列，请你在其中求出一段最长严格上升的部分，它不一定要连续。

就像这样：22, 33, 44, 77 和 22, 33, 44, 66 就是序列 22 55 33 44 11 77 66 的两个上升子序列，最长的长度是 44。在如下缺省代码情况下填空：

#include <stdio.h>
#include <stdlib.h>

#define N 100009
int f[N], a[N];
int n;

int find(int l, int r, int x)
{
    while (l < r)
    {
        int mid = (l + r) / 2;
        if (f[mid] < x)
        {
            l = mid + 1;
        }
        else
        {
            r = mid;
        }
    }
    return l;
}
int lis()
{
    int len = 0;
    for (int i = 0; i < n; i++)
    {     

## **/*在这里填写必要的代码*/**
   
        f[k] = a[i];
        if (k == len)
        {
            len++;
        }
    }
    return len;
}
int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", a + i);
    }
    printf("%d\n", lis());
    return 0;
}

答案：

int k = find(0,len,a[i]);

thank for you like!

赏

谢谢你de关爱

微信