本文共 2401 字，大约阅读时间需要 8 分钟。
一、最长递增子序列问题
1、动态规划法
设LIS[i]保存的是0到i（包括i）的最长递增子序列的元素个数
则LIS[i]=max{1,LIS[j]+1}0<=j<i
时间复杂度O(n^2)
//最长递增子序列#include #include #include #include using namespace std;#define MAX 100#define len 10int main() { int LIS[MAX]={0}; int arr[len]; int maxC=INT_MIN; generate(arr,arr+len,[](){return rand()%100;}); for_each(arr,arr+len,[](int i){cout< <<" ";}); cout< < len;++i) { LIS[i] = 1; for(int j = 0; j < i;++j) { if(arr[i] > arr[j] && LIS[j] + 1 > LIS[i]) { LIS[i] = LIS[j] + 1; } } maxC=max(maxC,LIS[i]); } cout< <
2、还有一种二分法，其实是一种贪心的策略，时间复杂度O(nlogn)
算法演示：
例如有数组arr={2,1,3,5,4}，最长递增序列长度可以看出是3
（1）取得第一个元素为2，LIS[0]=2，长度len=1
（2）取得第二个元素为1，1<2，贪心策略如下：如果2可以构成一个最长递增的序列，则1必然能构成最长递增序列，且1比2有更大的可能性，所以更新LIS[0]=2,len=1
（3）取得第三个元素为3，3>1，所以可以增加序列，此时LIS={0,3}，len=2
（4）取得第四个元素为5，5>3，增加序列，此时LIS={0,3,5}，len=3
（5）取得第五个元素为4，4在3和5之间，运用贪心策略，4比5更可能构成递增序列，所以更新5，有LIS={0,3,4},len=3
结束，输出len
可以看出，LiST中的元素始终是有序序列，所以在查找元素时，采用二分法
注：LIS数组中的元素并不是最长递增序列的解，保存的只是一种临时状态
//最长递增子序列二分法#include #include #include #include using namespace std;#define MAX 100#define len 10int main() { int LIS[MAX]={0}; int arr[len]; generate(arr,arr+len,[](){return rand()%100;}); for_each(arr,arr+len,[](int i){cout< <<" ";}); cout< < len;++i) { int left = 0; int right = maxC; while(left <=right) { int mid = (left+right)/2; if(LIS[mid] < arr[i]) left = mid +1; else right = mid -1; } LIS[left] = arr[i];//插入 if(left > maxC) { maxC++; } } cout< <
二、双端LIS问题 问题描述：
从一列数中筛除尽可能少的数使得从左往右看，这些数是从小到大再从大到小的。（网易）
这里采用动规求解，二分类似
设LIS1[i]保存的是0到i（包括i）递增子序列的元素个数，LIS2[i]保存的n到i（包括i）的递增子序列元素个数
则maxC=max{maxC,LIS1[i]+LIS2[i]-1} PS：因为i在这里算了两遍，所以-1
时间复杂度O(n^2)
//最长递增子序列#include #include #include #include using namespace std;#define MAX 100#define len 10int main() { int LIS1[MAX]={0}; int LIS2[MAX]={0}; int arr[len]; int maxC=INT_MIN; generate(arr,arr+len,[](){return rand()%100;}); for_each(arr,arr+len,[](int i){cout< <<" ";}); cout< < len;++i) { LIS1[i] = 1; for(int j = 0; j < i;++j) { if(arr[i] > arr[j] && LIS1[j] + 1 > LIS1[i]) { LIS1[i] = LIS1[j] + 1; } } } for(int i = len-1;i >= 0;--i) { LIS2[i] = 1; for(int j = len-1; j > i;--j) { if(arr[i] > arr[j] && LIS2[j] + 1 > LIS2[i]) { LIS2[i] = LIS2[j] + 1; } } maxC = max(maxC,LIS1[i]+LIS2[i]-1); } cout<
转载地址：http://jbvvi.baihongyu.com/