#include <iostream>using namespace std; #define MAXNUM 1000 char c[MAXNUM];char b[MAXNUM+1]; void solve(){     int i,first,last,mid,len;          len = 1;     i = 1;     b[1] = c[0];          while (c[i])     {         first = 1;         last = len+1;                  while (first < last)         {            mid = (first+last)>>1;            if (b[mid] < c[i])first = mid+1;            else last = mid;         }         b[first] = c[i++];         if (len < first)len = first;     }     cout << len << endl;} int main(){    cin >> c;    solve();    system("pause");    return 0;} ps:这是在看了别人的博客后自己试着去写的一个关于求最长递增子序列的程序。时间复杂度为O(nlogn).

评论