最长上升子序列（acwing 895 acwing 896 acwing1017）

理解

是动态规划的题目，就是找一个数组中存在的连续的子序列。

最长上升子序列（Longest Increasing Subsequence，LIS），在计算机科学上是指一个序列中最长的单调递增的子序列。 – 百度

acwing 895 最长上升子序列

点击跳转至acwing 895
f【】数组表示，当前位置最大能有多少连续的数构成子序列。

#include
#include
using namespace std ;
const int N = 1010 ;
int f[N] , a[N];
int main()
{
    int n ;
    cin >> n ;
    for(int i = 0 ; i < n ; i++)
    {
        cin >> a[i] ;
        f[i] = 1 ;
    }
    int res = 1;
    for(int i = 1 ; i < n ; i++)
    {
        for(int j = 0 ; j < i ; j++)
        {
            if(a[i] > a[j])
            {
                f[i] = max(f[i] , f[j] + 1);
            }
        }
        res = max(res,f[i]);
    }
    cout << res ;
    return 0 ;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

acwing 896 最长上升子序列2

点击跳转至acwing 896
优化：

思路：每次在q数组中找比a[i]小的最大的数，然后把这个数的下一位更新成a[i]（二分在l=mid的情况下，是要在模板上加1的，也就是右端点）

#include 
#include 

using namespace std;
const int N = 1e5 + 10;
int n;
int a[N], q[N];

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

    int len = 0;
    for(int i = 0; i < n; i ++){
        int l = 0, r = len; // 二分找到最大的小于当前数x的数c
        while(l < r){
            int mid = l + r + 1 >> 1;
            if(q[mid] < a[i]) l = mid;
            else r = mid - 1;
        }
        q[l + 1] = a[i];
        len = max(len , l + 1) ;
    }
    cout << len << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

acwing 1017 怪盗基德的滑翔翼

点击跳转至acwing 1017
在初始化的时候，直接在输入a数组值的时候就把f数组初始化。
思路：正反方向进行基础的LIS

#include
#include
#include
using namespace std ;
const int N = 110;
int a[N] , f[N];
int main()
{
    int k ;
    cin >> k ;
    while(k--)
    {
        int n ;
        cin >> n ;
        int res = 0 ;
        for(int i = 0;  i< n ; i++)
        {
            cin >> a[i] ;
            f[i] = 1 ;
        }
        for(int i = 1 ;  i< n ; i++)
        {
            for(int j = 0 ; j < i ; j++)
            {
                if(a[j] < a[i])
                {
                    f[i] = max(f[i] , f[j] + 1);
                }
            }
            res = max(res , f[i]);
        }
        for(int i = 0;  i< n ; i++)
        {
            f[i] = 1 ;
        }
        for(int i = n - 2;  i >= 0  ; i--)
        {
            for(int j = n - 1 ; j > i  ; j--)
            {
                if(a[j] < a[i])
                {
                    f[i] = max(f[i] , f[j] + 1) ;
                }
            }
            res = max(res , f[i]);
        }
        cout << res << endl;
    }
    return 0 ;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50