diff options
Diffstat (limited to 'content/math/longestIncreasingSubsequence.cpp')
| -rw-r--r-- | content/math/longestIncreasingSubsequence.cpp | 17 |
1 files changed, 17 insertions, 0 deletions
diff --git a/content/math/longestIncreasingSubsequence.cpp b/content/math/longestIncreasingSubsequence.cpp new file mode 100644 index 0000000..fcb63b4 --- /dev/null +++ b/content/math/longestIncreasingSubsequence.cpp @@ -0,0 +1,17 @@ +vector<int> lis(vector<ll>& a) { + int n = sz(a), len = 0; + vector<ll> dp(n, INF), dp_id(n), prev(n); + for (int i = 0; i < n; i++) { + int pos = lower_bound(all(dp), a[i]) - dp.begin(); + dp[pos] = a[i]; + dp_id[pos] = i; + prev[i] = pos ? dp_id[pos - 1] : -1; + len = max(len, pos + 1); + } + // reconstruction + vector<int> res(len); + for (int x = dp_id[len-1]; len--; x = prev[x]) { + res[len] = x; + } + return res; // indices of one LIS +} |