最長増加部分列

• Longest Increasing Subsequence; LIS
• 例えば数列$A=[2,4,1,3,3,5]$みたいなののLISは$[2,3,5]$と$[1,3,5]$
  • LISの長さは3
• DPとセグメントツリーで求まる
  • 計算量は$O(N\log N)$

実装

• DP（rust実装）
  • dp[j]を「今までに見た要素の中から取り出せる長さjの単調増加部分列における部分列の末尾の要素の最小値」とおく
  • dpの値は単調増加になるので二分探索により、あるiについてdp[i]を求めるのにO(logN)で求まる
  • LISはdpの長さに相当する

  fn main(){
  	let max_value: usize = (10_i32.pow(6)+ 1) as usize;
  	let mut A: Vec<usize> = vec![2,4,1,3,3,5];
  	let mut dp: Vec<usize> = vec![max_value;A.len()];
  	
  	for i in 0..A.len(){
  		let point = dp.binary_search(&A[i]).unwrap_or_else(|x| x);
  		dp[point] = A[i];
  	}
  	
  	println!("LIS: {}", dp.iter().position(|&x| x==max_value).unwrap_or(A.len()));
  }