【动态规划】最长上升子序列

Fivk

2022 年 01 月 07 日

1208 次浏览

暂无评论

1238字数

题目典例

给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少。

#### 输入格式

第一行包含整数 N。

第二行包含 N 个整数，表示完整序列。

#### 输出格式

输出一个整数，表示最大长度。

#### 数据范围

1≤N≤1000，
$−10^9$≤数列中的数≤$10^9$

#### 输入样例：

```
7
3 1 2 1 8 5 6
```

#### 输出样例：

```
4
```

#### 基本思考框架

![](https://blog.fivk.cn/usr/uploads/2022/01/2406788584.png)

#### 算法1

**(动态规划)** $O(n^2)$

- 状态表示：`f[i]`表示从第一个数字开始算，**以`w[i]`结尾的最大的上升序列**。(以`w[i]`结尾的所有上升序列中属性为最大值的那一个)
- 状态计算（集合划分）：$j∈(0,1,2,..,i-1)$, 在`w[i]` > `w[j]`时，$f[i] = max(f[i], f[j] + 1)$。
  有一个边界，若前面没有比i小的，`f[i`]为`1`（自己为结尾）。

最后在找`f[i]`的最大值。

**时间复杂度**
$O(n^2)$ 状态数$(n)$ * 转移数$(n)$

##### C++代码

```cpp
#include <bits/stdc++.h>
using namespace std;

const int N = 1e3+10;

int n;
int a[N], f[N];

int main() {

cin >> n;

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

for (int i = 1; i <= n; i++) {
	    f[i] = 1; // 只有a[i]一个数
	    for (int j = 1; j <= i; j++)
	        if (a[i] > a[j])
	            f[i] = max(f[i],f[j] + 1);
	}

int ans = 0;
	for (int i = 1; i <= n; i++)
	    if(f[i] > ans) ans = f[i]; 
	cout << ans;

return 0;
}
```

#### 算法2

**(动态规划 + 二分)** $O(nlogn)$

- 状态表示：`f[i]`表示**长度为`i`的最长上升子序列，末尾最小的数字**。(长度为`i`的最长上升子序列所有结尾中，结尾**最小`min`**的) 即长度为i的子序列末尾最小元素是什么。
- 状态计算：对于每一个`w[i]`, 如果大于`f[cnt-1]` *(下标从0开始，cnt长度的最长上升子序列，末尾最小的数字)*，那就`cnt+1`，使得最长上升序列长度`+1`，当前末尾最小元素为`w[i]`。 若`w[i]`小于等于`f[cnt-1]`,说明不会更新当前的长度，但之前末尾的最小元素要发生变化，找到第一个 大于或等于 (这里不能是大于) `w[i]`，更新以那时候末尾的最小元素。
- `f[i]`一定以一个单调递增的数组，所以可以用二分法来找第一个大于或等于w[i]的数字。

**时间复杂度**

- $O(nlogn)$ 状态数$(n)$ * 转移数$(logn)$

##### C++ 代码

```cpp
#include <iostream>

using namespace std;

const int N = 1010;
int n, cnt;
int w[N], f[N];

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

f[cnt++] = w[0];
    for (int i = 1; i < n; i++) {
        if (w[i] > f[cnt-1]) f[cnt++] = w[i];
        else {
            int l = 0, r = cnt - 1;
            while (l < r) {
                int mid = (l + r) >> 1;
                if (f[mid] >= w[i]) r = mid;
                else l = mid + 1;
            }
            f[r] = w[i];
        }
    }
    cout << cnt << endl;
    return 0;
}
```

最后修改：2022 年 01 月 07 日