最長増加部分列 LIS(Longest Increase Subsequence)

LIS

  • 最長増加部分列のこと
  • 部分列において、狭義単調増加(a1 < a2 < a3 ... )
    • 広義VERもある(下記)

解説

verify✅

感想

  • 配列Lは単調増加
    • なので後端だけ見る or 二分探索で高速に更新箇所を決められる
  • ※配列LはLISではないことに注意

関連問題

関数化

ll LIS(VI& A){
  ll N = A.size();
  VI L;
  L.push_back(A[0]);
  FOR(i, 1, N){
    ll a = A[i];
    if(L.back()<a){
      L.push_back(a);
    }else{
      auto it = lower_bound(ALL(L), a);
      *it = a;
    }
  }
  return L.size();
}

LIS復元

// sortedな列から検索。0-indexed
// xの書き込み先を返す
ll index_of(VI& A, ll x){
  return distance(A.begin(), lower_bound(A.begin(), A.end(), x));
}
// 復元可能
// http://www.prefield.com/algorithm/dp/lis_fast.html
VI LIS(VI& a) {
  const int n = a.size();
  VI A(n, inf);
  VI id(n); // Aのどこに挿入したかの情報
  rep(i,n){
    id[i] = index_of(A, a[i]);
    A[ id[i] ] = a[i];
  }
  int m = *max_element(id.begin(), id.end());
  VI b(m+1);
  // 後ろから
  for (int i = n-1; i >= 0; --i)
    if (id[i] == m){
      b[m] = a[i];
      m--;
    }
  return b;
}
int main(){
    VI A = {5,3,7,4,1};
    auto a = LIS(A);
    debug(a);
    return 0;
}

出力

{3, 4}
  • 参考先のを自分用に書き換えたもの。補助配列idを使うことで正しく復元できている
  • TODO verify用問題

広義単調LIS

  • a1 <= a2 <= a3 ... とイコールを許す
ll LIS2(VI& A){
  ll N = A.size();
  VI V;
  V.push_back(A[0]);
  FOR(i, 1, N){
    ll a = A[i];
    if(V.back()<=a){
    //if(V.back()<a){
      V.push_back(a);
    }else{
      // auto it = lower_bound(ALL(V), a);
      auto it = upper_bound(ALL(V), a);
      *it = a;
    }
  }
  debug(V);
  return V.size();
}

関連問題