最长上升子序列

#最长上升子序列| 来源: 网络整理| 查看: 265

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

输入格式第一行包含整数N。

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

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

数据范围 1≤N≤1000， −109≤数列中的数≤109 输入样例：

7 3 1 2 1 8 5 6

输出样例：

4 思路

在这里插入图片描述

此处要分析动态规划中的状态表示，f[i]的意义是以第i个为结尾的上升子序列，而我们需要求的属性是MAX，对于f[i]我们可以划分为以i之前一个数为结尾的上升子序列 + 1，此处需满足条件是a[i] > a[j]. 最后需要遍历所有f，来存一个最大值

#include #include using namespace std; const int N = 1010; int n; int a[N], f[N];//f[i]表示所有以i结尾的严格单调上升的子序列的最大长度 int main() { scanf("%d", &n); for (int i = 1; i scanf("%d", &n); for (int i = 0; i int mid = l + r + 1 >> 1; if (q[mid]

【本文地址】

公司简介

联系我们