123456789101112131415161718192021222324252627282930313233343536373839404142434445464748 |
- // Given a list of numbers of length n, this routine extracts a
- // longest increasing subsequence.
- //
- // Running time: O(n log n)
- //
- // INPUT: a vector of integers
- // OUTPUT: a vector containing the longest increasing subsequence
- #include <iostream>
- #include <vector>
- #include <algorithm>
- using namespace std;
- typedef vector<int> VI;
- typedef pair<int,int> PII;
- typedef vector<PII> VPII;
- #define STRICTLY_INCREASNG
- VI LongestIncreasingSubsequence(VI v) {
- VPII best;
- VI dad(v.size(), -1);
-
- for (int i = 0; i < v.size(); i++) {
- #ifdef STRICTLY_INCREASNG
- PII item = make_pair(v[i], 0);
- VPII::iterator it = lower_bound(best.begin(), best.end(), item);
- item.second = i;
- #else
- PII item = make_pair(v[i], i);
- VPII::iterator it = upper_bound(best.begin(), best.end(), item);
- #endif
- if (it == best.end()) {
- dad[i] = (best.size() == 0 ? -1 : best.back().second);
- best.push_back(item);
- } else {
- dad[i] = dad[it->second];
- *it = item;
- }
- }
-
- VI ret;
- for (int i = best.back().second; i >= 0; i = dad[i])
- ret.push_back(v[i]);
- reverse(ret.begin(), ret.end());
- return ret;
- }
|