{"comment":{"url":"https://api.github.com/repos/zhaozhaoxia/LIS-O-nlogn-/comments/12783155","html_url":"https://github.com/zhaozhaoxia/LIS-O-nlogn-/commit/f6b6d2762871cd41f8644f5544cb4367236a0a93#commitcomment-12783155","id":12783155,"user":{"login":"zhaozhaoxia","id":6340124,"avatar_url":"https://avatars.githubusercontent.com/u/6340124?v=3","gravatar_id":"","url":"https://api.github.com/users/zhaozhaoxia","html_url":"https://github.com/zhaozhaoxia","followers_url":"https://api.github.com/users/zhaozhaoxia/followers","following_url":"https://api.github.com/users/zhaozhaoxia/following{/other_user}","gists_url":"https://api.github.com/users/zhaozhaoxia/gists{/gist_id}","starred_url":"https://api.github.com/users/zhaozhaoxia/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/zhaozhaoxia/subscriptions","organizations_url":"https://api.github.com/users/zhaozhaoxia/orgs","repos_url":"https://api.github.com/users/zhaozhaoxia/repos","events_url":"https://api.github.com/users/zhaozhaoxia/events{/privacy}","received_events_url":"https://api.github.com/users/zhaozhaoxia/received_events","type":"User","site_admin":false},"position":null,"line":null,"path":"","commit_id":"f6b6d2762871cd41f8644f5544cb4367236a0a93","created_at":"2015-08-19T12:48:55Z","updated_at":"2015-08-19T12:48:55Z","body":"//LIS在O(nlogn)的情况下的解法\r\n#include <iostream>\r\n#include <vector>\r\nusing namespace std;\r\n\r\nint LIS(vector<int>& num)\r\n{\r\n      int length = num.size();\r\n      vector<int> f;\r\n      vector<int>::iterator iv;\r\n      f.reverse(length);\r\n      for(int i=0;i<length;i++)\r\n      {\r\n             if(f.empty())\r\n                  f.push_back(num[i]);\r\n             else\r\n            {\r\n                  iv = find(f.begin().f.end(),num[i]);//折半查找;\r\n                  if(iv!=f.end())\r\n                        *iv = num[i];\r\n                  else\r\n                        f.push_back(num[i]);\r\n            }\r\n       }\r\n       return f.size();\r\n}\r\n\r\nint main()\r\n{\r\n       vector<int>  num;\r\n        int temp;\r\n        while(cin>>temp)\r\n        {\r\n                  num.push_back(temp);\r\n        }\r\n        return LIS(num);\r\n}\r\n\r\n\r\n"}}