Skip to content

Instantly share code, notes, and snippets.

@maehrm

maehrm/DPL_1_D.rb

Created February 28, 2018 12:53
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save maehrm/4df4aa3d2a55e537e589b9e6dd9758d8 to your computer and use it in GitHub Desktop.
Save maehrm/4df4aa3d2a55e537e589b9e6dd9758d8 to your computer and use it in GitHub Desktop.
Download ZIP
Longest Increasing Subsequence | Aizu Online Judge http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_D
Raw
DPL_1_D.rb
dp, a = [], []
n = gets.to_i
n.times {
a << gets.to_i
dp << 1e9+1
}
a.each_index{|i|
dp[dp.bsearch_index {|x| x >= a[i]}] = a[i]
}
ans = dp.bsearch_index {|x| x >= 1e9+1 }
puts ans.nil? ? dp.size : ans
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment