最长递增子序列（LIS）
之前我只知道用dp来找LIS，复杂度为O（n2），但最近学习了一种复杂度为O（nlogn）的方法。
1.dp
用dp[i]=max(dp[j]+1),其中j满足j<i&&a[j]<a[i]条件时，进行转移。
程序如下：
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 5 using namespace std; 6 7 const int maxn = 1e5 + 10; 8 9 int a[maxn]; 10 int dp[maxn]; 11 12 int main() 13 { 14 int n; 15 while (scanf("%d", &n) != EOF) 16 { 17 for (int i = 0; i < n; i++) 18 { 19 scanf("%d", &a[i]); 20 } 21 dp[0] = 1; 22 int ma = 1; 23 for (int i = 1; i < n; i++) 24 { 25 dp[i] = 1; 26 for (int j = 0; j < i; j++) 27 { 28 if(a[i] > a[j]) 29 { 30 dp[i] = max(dp[i], dp[j] + 1); 31 } 32 } 33 ma = max(ma, dp[i]); 34 } 35 printf("%d ", ma); 36 } 37 38 39 return 0; 40 }
2.算法2
维护一个数组v，保持这个数组单调递增的性质，把原数组a的数按顺序放入到v中，
当a当前的数大于v的最后一个数时，直接把该数添加到v的末尾，
否则就利用二分查找，把数替代v中第一个比它大的数，复杂度O（logn）。
最后v数组的长度为最长递增序列。
而复杂度就是O（nlogn）。
1 #include <cstdio> 2 #include <cstring> 3 #include <vector> 4 #include <algorithm> 5 6 using namespace std; 7 8 const int maxn = 1e5 + 10; 9 10 int v[maxn]; 11 int a[maxn]; 12 13 int binary_search(int left, int right, int value) 14 { 15 while (left <= right) 16 { 17 int mid = (right + left) / 2; 18 if (v[mid] > value) 19 { 20 right = mid - 1; 21 } 22 else if (v[mid] < value) 23 { 24 left = mid + 1; 25 } 26 else 27 { 28 return mid; 29 } 30 } 31 return left; 32 } 33 34 int main() 35 { 36 int n; 37 while (scanf("%d", &n) != EOF) 38 { 39 int len = 1; 40 for (int i = 0; i < n; i++) 41 { 42 scanf("%d", &a[i]); 43 } 44 v[0] = a[0]; 45 for (int i = 1; i < n; i++) 46 { 47 if (a[i] > v[len - 1]) 48 { 49 v[len] = a[i]; 50 len++; 51 } 52 else 53 { 54 int p = binary_search(0, len - 1, a[i]); 55 v[p] = a[i]; 56 } 57 } 58 printf("%d ", len); 59 } 60 61 return 0; 62 }