# Dynamic programming the longest common ascending subsequence-n ^ 2 solution

2021-03-26 03:22:13 Kocoder

## 1. Title Description

Given two sequences $$A, B$$, If they all contain a number whose position is not necessarily continuous , And the value is strictly increasing , Then we call this segment a common ascending subsequence of two sequences . seek $$A$$ and $$B$$ The longest common ascending subsequence of .

Input format

The first line contains an integer $$N$$, Express $$A$$ and $$B$$ The length of .

The second line contains $$N$$ It's an integer , Represents a sequence of numbers $$A$$.

The third line contains $$N$$ It's an integer , Represents a sequence of numbers $$B$$.

Output format

Output an integer , Represents the length of the longest common ascending subsequence .

Data range

$$1 ≤ N≤ 3000$$, No number in the sequence exceeds $$2^{31} - 1$$.

sample input

4
2 2 1 3
2 1 2 3


sample output

2


## 2. Simple solution $$O(n^3)$$

The naive solution combines the longest common subsequence with the longest ascending subsequence model .

use $$f[i][j]$$ Represents the front of the first sequence $$i$$ Number , And the front of the second sequence $$j$$ Number , And the last number is $$b[j]$$ The length of the longest common ascending subsequence of .

According to $$a[i]$$ Is it equal to $$b[j]$$ Have a classified discussion .

$f[i][j]=\left\{ \begin{array}{rcl} f[i - 1][j] & & {a[i] != a[j]}\\ max_{k < j And b[k] < b[j]}(f[i][j], f[i- 1][k]) & & {a[i] == b[j] }\\ \end{array} \right.$

#include <iostream>
#include <algorithm>

using namespace std;
const int N = 3010;
int a[N], b[N];
int n;
int f[N][N];

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

for(int i = 1; i <= n; i ++)
{
for(int j = 1; j <= n; j ++)
{
f[i][j] = f[i - 1][j];
if(a[i] == b[j])
{
f[i][j] = max(f[i][j], 1);
for(int k = 1; k < j; k ++)
if(b[k] < b[j]) f[i][j] = max(f[i][j], f[i - 1][k] + 1);
}
}
}
int res = 0;
for(int i = 1;i <= n; i ++) res = max(res, f[n][i]);
cout << res << endl;
return 0;
}


## 3. Code optimization $$O(n^2)$$

The time complexity of the above simple method is $$O(n^3)$$. So how do we optimize ?

• Look at the innermost loop of the code

 if(a[i] == b[j])
{
f[i][j] = max(f[i][j], 1);
for(int k = 1; k < j; k ++)
if(b[k] < b[j]) f[i][j] = max(f[i][j], f[i - 1][k] + 1);
}


Because when you execute the innermost loop a[i] == b[j]. So the innermost condition can be changed to b[k] < a[i].

• Consider the whole cycle

for(int i = 1; i <= n; i ++)
{
for(int j = 1; j <= n; j ++)
{
f[i][j] = f[i - 1][j];
if(a[i] == b[j])
{
f[i][j] = max(f[i][j], 1);
for(int k = 1; k < j; k ++)
if(b[k] < a[i]) f[i][j] = max(f[i][j], f[i - 1][k] + 1);
}
}
}


We're actually asking for ： When the first cycle comes to i, The second cycle goes to j And meet " a[i] > b[k] And k < j " when f[i - 1][j] The maximum of .

That is to say, when we visit the second j When the layers loop , Before need j-1 Layer data . therefore , Can be in j In the loop of .

The code is as follows

for(int i = 1; i <= n; i ++)
{
int maxv = 1;
for(int j = 1; j <= n; j ++)
{
f[i][j] = f[i - 1][j];
if(a[i] == b[j]) f[i][j] = max(f[i][j],maxv);
if(b[j] < a[i]) maxv = max(maxv, f[i - 1][j] + 1);  // maxv The update of must be in f[i][j] After the update of .
}
}


## 4. summary

• This problem is a combination of the longest common subsequence model and the longest ascending subsequence model , We can use Longest ascending subsequence And the longest common subsequence , State representation and state transition equation are constructed .
• The time complexity of the naive solution is high , But we can optimize according to the code , The complexity of time is determined by $$O(n^3)$$ drop to $$O(n^2)$$.

https://chowdera.com/2021/03/20210311213904136k.html