LIS完全に理解した ~最長増加部分列(Longest Increase Subsequence)~

LIS

最長増加部分列のこと

解説

https://ikatakos.com/pot/programming_algorithm/dynamic_programming/longest_common_subsequence

問題を解いてVerify

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3776378#1

計算量

O(N logN)

感想

  • 配列Lは単調増加になっている
    • なので後端だけ見ればいい
    • lower_boundも可能
    • 芸術的
    • (※配列Lは常にLISが入っているわけではない。L=[1,4]になった箇所など)

Note

f:id:peroon:20190727051548j:plain

    ll N;
    cin >> N;

    vector<ll> A(N);
    FOR(i, 0, N){
        cin >> A.at(i);
    }

    vector<ll> 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;
        }
    }

    ll ans = L.size();

関連問題

関数化した (バグあり)

// LISとして求まったvectorを返す
VI LIS_bad(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){
      V.push_back(a);
    }else{
      auto it = lower_bound(ALL(V), a);
      *it = a;
    }
  }
  return V;
}
  • verified D - トランプ挿入ソート https://atcoder.jp/contests/abc006/submissions/9288854
  • ※追記:正しいLISが求まらないことがある
    • 例:A = {5,3,7,4,1}としたときに{1,4}を返してしまう
  • 長ささえ求まればいいのなら、これでいい?

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を使うことで正しく復元できている

広義単調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();
}