最长上升子序列

C++ STL 求向量中的最大值和最小值min_element(v.begin(),v.end()) max_element(v.begin(),v.end()) sizeof(n)/sizeof(int) min_element 算法返回最小的元素的位置中序列 [first, last)。

问题描述

一个数的序列ai，当a 1 < a 2 < … < a S 的时候，我们称这个序列是上升的。对于给定的一个序列(a 1 , a 2 , …, a N )，我们可 以得到一些上升的子序列(a i1 , a i2 , …, a iK )，这里1 <= i1

“求以a k （k=1, 2, 3…N）为终点的最长上升子序列的长度”一个上升子序列中最右边的那个数，称为该子序列的“终点”。

** 虽然这个子问题和原问题形式上并不完全一样，但是只要这N个子问题都解决了，那么这N个子问题的解中，最大的那个就是整个问题的解。

2. 确定状态： 子问题只和一个变量– 数字的位置相关。因此序列中数的位置k 就是“状态”，而状态 k 对应的“值”，就是以a k做为“终点”的最长上升子序列的长度。状态一共有N个。

3. 找出状态转移方程： maxLen (k)表示以a k 做为“终点”的最长上升子序列的长度那么：初始状态：

maxLen (1) = 1 maxLen (k) = max { maxLen (i)：1<=i < k 且 a i < a k 且 k≠1 } + 1

若找不到这样的i,则maxLen(k) = 1 maxLen(k)的值，就是在a k 左边，“终点”数值小于a k ，且长度最大的那个上升子序列的长度再加1。因为a k 左边任何“终点”小于a k 的子序列，加上a k 后就能形成一个更长的上升子序列。

“人人为我”递推型动归程序

#include <iostream> #include <algorithm> #include <cstring> #define MAX 1010 using namespace std; int a[MAX], maxLen[MAX]; int main() { int N; cin >> N; for(int i=1; i<=N; i++) { cin >> a[i]; maxLen[i] = 1; } for(int i=2; i<=N; i++) { for(int j=1; j<i; j++) { if(a[i] > a[j]) maxLen[i] = max(maxLen[i], maxLen[j]+1);//注意这里要取maxLen[i] 和 maxLen[j]+1的最大值 如果不是这样，见图片后果 } } cout << *max_element(maxLen+1, maxLen+N+1); return 0; }

对应51NOD 1134

#include <iostream> #include <stdio.h> #include <algorithm> using namespace std; #define N 50010 int A[N]; int B[N]; int Upper_bound(int len, int A) { int i; for(i=0; i<len; i++) { if(B[i] > A) return i; } return i; } int List(int n) { B[0] = A[0]; int len =1; for(int i=1; i<n; i++) { B[ A[i]>B[len-1]? len++:Upper_bound(len, A[i]) ] = A[i]; } return len; } int main() { int n; scanf("%d", &n); for(int i=0; i<n; i++) scanf("%d", &A[i]); printf("%d", List(n)); return 0; }

C++有类似STL

lower_bound(first, last, val)算法返回一个非递减序列[first, last)中的第一个大于等于值val的位置。

upper_bound(first, last, val)算法返回一个非递减序列[first, last)中第一个大于val的位置。

ReCclay 认证博客专家 嵌入式软件开发 机器/深度学习 全栈技术学习者 大家好，我是博主ReCclay，目前处于研究生阶段，就读于电子科技大学，主攻方向为汽车辅助驾驶算法研究。入站以来，凭借坚持与热爱，以博文的方式分享所学，截止目前累计博文数量达800余篇，累计受益人次达130w+次，涉及领域包括但不限于物联网开发、单片机开发、Linux驱动开发、FPGA开发、前/后端软件开发等。在未来我将继续专注于嵌入式相关领域，学习更多的科技知识，输出更高质量的博文。