先发个程序：
#include <iostream> #include <cstring> #include <cstdio> using namespace std; int main() { int a[1001], b[1001], i, j, k, n; cin>>n; for(i = 1; i <= n; i++) cin>>a[i]; k=1; b[1]=a[1]; for(i=2;i<=n;i++) { if(a[i]>b[k]) b[++k]=a[i]; else { j=k; while(a[i]<=b[j])//这个while循环是关键 j--; b[j+1]=a[i]; } } cout<<k<<endl; return 0; }
调试下这个程序你就知道用二分搜索算法做这题的基本思想了；
而二分搜索算法就是把上面while循环改进了一下；
代码：
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #define maxn 1008 #define inf 10001; using namespace std; int s[maxn], a[maxn]; //二分法搜索digit，若s中存在digit，返回其下标；若不存在，返回s中比digit小的 最大的那个数的 下标加1； int binary_serch(int digit, int len) { int left = 0, right = len, mid; while(left != right) { mid = (left + right)/2; if(digit == s[mid]) return mid; else if(digit < s[mid]) right = mid; else left = mid+1; } return left; } int main() { int i, j, n, k; while(~scanf("%d", &n)) { for(i = 0; i < n; i++) scanf("%d", &a[i]); s[0] = a[0]; k = 1; for(i = 1; i < n; i++) { s[k] = inf; j = binary_serch(a[i], k); if (j == k) k++; s[j] = a[i]; } cout<<k<<endl; } return 0; }