普通的思路是O(n2)的复杂度，这个题的数据量太大，超时，这时候就得用nlogn的复杂度的算法来做，这个算法的主要思想是只保存有效的序列，即最大递增子序列，然后最后得到数组的长度就是最大子序列。比如序列7 8 9 1 2 3 来说， 就是先把第一个数输入到数组中，然后继续输入后面的数，每输入一个数都要和最后一个数比较，因为这时最后一个数一定是有效序列中最大的，如果大于最后一个数，那么就直接将它放到数组的最后就行了，如果不大于最后一个数的话，就找到第一个比他大的数，然后替换它，样例中，先输入进去7， 然后再输入8，因为8 > 7， 所以直接将8放到数组的最后，同理，9也是，当输入到1的时候，判断它不比9大，这时候就需要找第一个比1大的数，这时候就用二分查找就行了，因为这个数组这样输入进去的话，肯定是有序的，找到第一个比他大的数是7，那么就替换7，现在数组中的元素分别是1, 8, 9,继续输入2，判断它不比数组的最后一个元素大，这时候继续二分找第一个比它大的，那么将替换8，同理3将会替换9，最后数组的元素分别是1， 2， 3,这是用贪心的策略来做的，因为只有保存最小的，后面的数组成最长序列的机会才会更大，所以要保存最小的.
再比如：1 8 2 4 5 先将1保存到数组中，然后再将8保存到数组中，继续判断2，不大于最后一个元素，所以找第一个比它大的，替换8，至于为什么是这样，因为同样是序列长度为2的，1 2这个序列当然要比1 8 可能的序列要长，因为后面有4，如果1 8 的话就不能长度再加一了，所以更新最小的
代码如下;
#include <iostream> #include <stdio.h> #include <string.h> #include <vector> using namespace std; const int N = 100000 + 10; int a[N];//保存当前最大的序列 int e;//表示当前数组中有几个元素 void replace_value(int n)//二分法查找替换 { int left = 0, right = e; int mid = (left + right) >> 1; while (left < right) { if (left + 1 == right) { if (a[right] != n)//替换右值 a[right] = n; return; } if (a[mid] == n) return; if (a[mid] > n) right = mid; else left = mid; mid = (left + right) >> 1; } } int main() { int n; while (~scanf("%d", &n)) { e = 0; memset(a, 0, sizeof(a)); a[0] = -2147483648; int t; for (int i = 0; i < n; i++) { scanf("%d", &t); if (t > a[e])//如果大于当前已有的数中最大的， 就将它添加到数组中 a[++e] = t; else replace_value(t); } cout << e << endl; } return 0; }
下面这个代码的思想和上面的基本相同，我是看的网上的，大体思路就是先将数据输入到一个数组中，然后在一个一个的判断，找每个元素应该在的位置，也就是上面的那种思想，不过不如上面的那个简单
#include <stdio.h> const int N = 100000 + 10; int a[N], b[N];//a来存放输入的元素，b来存放当前最长子序列元素 //寻找n所在b当中的位置，二分查找，时间复杂度logn; int search_pos(int n, int len) { int left = 1, right = len; int mid = (left + right) >> 1; while (left <= right) { if (b[mid] == n) return mid; else if (b[mid] < n) left = mid + 1; else right = mid - 1; mid = (left + right) >> 1; } return left; } int main() { int n; while (~scanf("%d", &n)) { for (int i = 0; i < n; i++) scanf("%d", &a[i]); b[1] = a[0]; int len = 1; int j; for (int i = 1; i < n; i++) { j = search_pos(a[i], len);//找到第一个比他大的位置，如果已经是最大，那么就是b数组的最后一个位置 b[j] = a[i]; if (j > len)//如果是最后一个位置，len更新为j len = j; } printf("%d ", len); } return 0; }