最长上升子序列模板

算法思想：失之东隅，收之桑隅

对于一个序列，它正向最长上升子序列的长度就是它反向最长下降子序列的个数。

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 #include<string.h>
 4 #include<math.h>
 5 #include<algorithm>
 6 #include<queue>
 7 #include<stack>
 8 #include<deque>
 9 #include<iostream>
10 using namespace std;
11 typedef long long  LL;
12 int con[30009];
13 int dp[30009];
14 int p;
15 int Binary_search(int target)
16 {
17     int left=0,right=p;
18     int index=0;
19     while(left<=right)
20     {
21         int mid=(left+right)/2;
22         if(dp[mid]<target)
23             left=mid+1;
24         else
25         {
26             right=mid-1;
27             index=mid;
28         }
29     }
30     return index;
31 }
32 int main()
33 {
34     int i,j;
35     int n;
36     p=0;
37     scanf("%d",&n);
38     for(i=0;i<n;i++)
39         scanf("%d",&con[i]);
40     dp[0]=con[0];
41     for(i=1;i<n;i++)
42     {
43         if(con[i]>dp[p])
44             dp[++p]=con[i];
45         else
46         {
47             int mid=Binary_search(con[i]);
48             dp[mid]=min(dp[mid],con[i]);
49         }
50     }
51     printf("%d
",p+1);
52     return 0;
53 }