时间复杂度为 n*logn的LIS算法是用一个stack维护一个最长递增子序列
如果存在 x < y 且 a[x] > a[y],那么我们可以用a[y]去替换a[x]
因为a[y]比较小，具有更大的潜力，使得后面的元素和它成为更长的递增序列
如例子： a[] = {1,4,8,3,6};
我们用一个stack st保存当前的最长递增子序列,top = 0;
很明显，初始化时st[top] = 1;
之后随着i循环变量的递增，如果
a[i] > st[top] , 那么 st[++top] = a[i]. 很显然top+1就是当前最长递增子序列的长度
这样子判断的时间复杂度是O(1)，
为什么可以这样子判断？？？
因为st保存的是当前的最长递增子序列，所以如果a[i] > st[top] 那么a[i]可以加入st中
从而形成更长的最长递增子序列。
那么可能会有想法是，如果数据是1 5 3 4，很明显，最长递增子序列是1 3 4，
但是根据上面的想法是 1 5 形成最长递增子序列。
别担心
下面介绍 当 a[i] < st[top]时的处理方法
上面我们说过， 如果存在x < y 且 a[x] > a[y] 我们可以使用a[y]去替换a[x]
因为a[y] 具有更大的潜力,使得后面的元素和它成为更长的递增序列。
所以当 a[i] < st[top]时， 显然 st中的元素就是a[x],而a[i]就是a[y]
我们在st中使用二分查找找到第一个大于等于a[i]的元素，然后用a[i]去替换它
比如 st = 1 , 4 , 8时
a[i] = 3,
我们可以用a[i]去替换4，从而在不影响结果的前提下，减少时间复杂度
题目uva10534
给定一个一组数字，要我们求这样一个序列
在序列的左边是递增的，右边是递减的，且递增和递减的个数要是一样的
思路：分别从两边进行最长递增子序列的dp，
dp1是从下标 0 -> n-1 进行dp
dp2是从下标 n-1 -> 0 进行dp
所以 ans = max{ min(dp1[i]-1, dp2[i]-1)+1, 0<=i<n };
但是题目的数据有1w，O(N*N）的算法是不行的，
所以要用nlogn的算法
1 #include <stdio.h> 2 #include <string.h> 3 #include <stdlib.h> 4 #include <algorithm> 5 #include <iostream> 6 #include <queue> 7 #include <stack> 8 #include <vector> 9 #include <map> 10 #include <set> 11 #include <string> 12 using namespace std; 13 typedef long long LL; 14 const int INF = 1<<30; 15 const int N = 10000 + 10; 16 int min(const int &a, const int &b) 17 { 18 return a < b ? a :b; 19 } 20 int max(const int &a, const int &b) 21 { 22 return a < b ? b : a; 23 } 24 int st[N]; 25 int top; 26 void LIS(int *a, int n, int *dp) 27 { 28 int i,j; 29 top = 0; 30 st[top] = a[0]; 31 for(i=1; i<n; ++i) 32 { 33 if(a[i] > st[top]) 34 { 35 st[++top] = a[i]; 36 dp[i] = top +1 ; 37 } 38 else 39 { 40 int low = 0, high = top; 41 while(low <= high) 42 { 43 int mid = (low + high) >> 1; 44 if(st[mid]<a[i]) 45 low = mid + 1; 46 else 47 high = mid - 1; 48 } 49 st[low] = a[i]; 50 dp[i] = low +1; 51 } 52 } 53 } 54 int a[N]; 55 int dp[2][N]; 56 int main() 57 { 58 int n,i,j; 59 while(scanf("%d",&n)!=EOF) 60 { 61 for(i=0; i<n; ++i) 62 { 63 scanf("%d",&a[i]); 64 dp[0][i] = dp[1][i] = 1; 65 } 66 LIS(a,n,dp[0]); 67 68 int low = 0,high = n - 1; 69 while(low < high) 70 { 71 int t = a[low]; 72 a[low] = a[high]; 73 a[high] = t; 74 low ++; 75 high --; 76 } 77 LIS(a,n,dp[1]); 78 79 int ans = 0; 80 for(i=0; i<n; ++i) 81 { 82 int t = 2 * min(dp[0][i]-1,dp[1][n-i-1]-1) +1;//因为第二次dp是将数组倒过来dp，所以要n-i-1 83 ans = max(ans,t); 84 } 85 printf("%d ",ans); 86 } 87 return 0; 88 }