Skip to content

Instantly share code, notes, and snippets.

@Chillee

Chillee/lis.cpp

Last active November 14, 2018 00:36
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save Chillee/8c35dce0bd710fb35e6bd6f3bd98be90 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save Chillee/8c35dce0bd710fb35e6bd6f3bd98be90 to your computer and use it in GitHub Desktop.
Download ZIP
Longest Increasing Subsequence(LIS)
Raw
lis.cpp
vector<int> ans;
for (auto x : A) {
auto it = lower_bound(ans.begin(), ans.end(), x);
if (it == ans.end())
ans.push_back(x);
else
*it = x;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment