diff options
Diffstat (limited to 'math/longestIncreasingSubsequence.cpp')
| -rw-r--r-- | math/longestIncreasingSubsequence.cpp | 17 |
1 files changed, 0 insertions, 17 deletions
diff --git a/math/longestIncreasingSubsequence.cpp b/math/longestIncreasingSubsequence.cpp deleted file mode 100644 index fcb63b4..0000000 --- a/math/longestIncreasingSubsequence.cpp +++ /dev/null @@ -1,17 +0,0 @@ -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 -} |