All in one 1281 Dynamic programming of the longest ascending subsequence solution

Topic link ：​ ​http://ybt.ssoier.cn:8088/problem_show.php?pid=1281​​

The main idea of the topic ：

I'll give you a sequence \(a_1, a_2, \ldots, a_n\), You need to find some subscripts in the sequence \(i_1, i_2, \ldots, i_k\) At the same time satisfy ：

• \(1 \le i_1 \lt i_2 \lt \ldots \lt i_k \le n\);
• \(a_{i_1} \lt a_{i_2} \lt \ldots \lt a_{i_k}\)

namely ： Find out a subsequence of the sequence that each element in the subsequence is smaller than the element after it .

The longest subsequence that satisfies this property （ Contains up to ） The subsequence of is called the sequence of numbers “ Longest ascending subsequence ” .

notes ：“ Longest ascending subsequence ” English is “Longest increasing subsequence”, abbreviation “LIS”, So we usually put “ Longest ascending subsequence ” The problem is abbreviated as LIS problem .

What this problem solves is the length of the longest ascending subsequence .

Their thinking ：

This problem is solved by dynamic programming （ Attention, everyone ： And then I'm going to “LIS” To express “ Longest ascending subsequence ” 了 ）.

Define the State \(f_i\) Said to \(a_i\) At the end of the LIS length .

Be careful ： here “ With \(a_i\) ending ” It means this LIS Must contain \(a_i\)（ in other words \(a_i\) yes LIS The last element in ）

The first thing you can be sure of is \(f_i\) At least for \(1\)（ because \(a_i\) A single number can form a length of \(1\) Of LIS）.

Secondly, we can think of the words , For any \(j(1 \le j \lt i)\), if \(a_j \lt a_i\), be \(a_i\) You can follow \(a_j\) Then a ascending subsequence is formed , And then \(a_j\) At the end of the LIS The length is \(f_j\), be \(a_i\) With the \(a_j\) What can be formed later LIS The length is \(f_j + 1\).

Accordingly , We can derive the state transition equation as follows ：

\(f_i = \max\limits_{j = 1 \text{ to }i-1 \text{ and } a_j \lt a_i} \{ f_j \} + 1\)

And \(f_i\) At least for \(1\).

Find all the \(f_i(1 \le i \le n)\) after , We can find out , Of this series LIS It must be in some way \(a_i\) At the end of the , So we can get the LIS by \(\max\limits_{i = 1 \text{ to } n}\{ f_i \}\) .

The example program is as follows ：

Log in and copy

      
      

       
       #include <bits/stdc++.h>
       
       
using namespace std;
       
       
const int maxn = 1010;
       
       
int n, a[maxn], f[maxn], ans;
       
       
int main()
       
       
{
       
       
    scanf("%d", &n);
       
       
    for (int i = 1; i <= n; i ++)
       
       
        scanf("%d", a+i);
       
       
    for (int i = 1; i <= n; i ++)
       
       
    {
       
       
        f[i] = 1;
       
       
        for (int j = 1; j < i; j ++)
       
       
            if (a[j] < a[i])
       
       
                f[i] = max(f[i], f[j] + 1);
       
       
    }
       
       
    for (int i = 1; i <= n; i ++)
       
       
        ans = max(ans, f[i]);
       
       
    printf("%d\n", ans);
       
       
    return 0;
       
       
}
      
      
      
      

       
       
1.
       
       
2.
       
       
3.
       
       
4.
       
       
5.
       
       
6.
       
       
7.
       
       
8.
       
       
9.
       
       
10.
       
       
11.
       
       
12.
       
       
13.
       
       
14.
       
       
15.
       
       
16.
       
       
17.
       
       
18.
       
       
19.
       
       
20.
       
       
21.
      
      

The time complexity of the above code is \(O(n^2)\), And for LIS The problem has a binary optimization \(O(n \cdot log n)\) Algorithm , Interested students can study it by themselves .