# 目次

• 目次
• 問題
• 解説
• 計算量
  • 解答1
  • 解答2
• 解答1
• 解答2

# 問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_D

増加部分列とは、ランダムに並んだ数列の先頭から順に要素が必ず大きくなっていくように要素を選んだ数列のこと.
そのうち、一番長く要素を選ぶことが出来た数列を最長増加部分列（以下、LIS）という.

例えば、 2 5 4 6という数列であれば、

増加部分列は、

• 2
• 5
• 4
• 6
• 2 5
• 2 4
• 2 6
• 5 6
• 4 6
• 2 5 6
• 2 4 6

となるので、最長は最後の２つなので長さは３.

# 解説

LISを格納する空のコンテナを用意する.
数列を先頭から要素xを取り出して、

1. LISが空ならLISにxを加える <-- ベースケース
2. LIS最後の要素 < xであればLISの末尾にxを加える
3. x <= LIS最後の要素であれば増加列を崩さないぎりぎり最初の要素をxに置き換える

手順3ではLISは昇順にソート済みのはずなので二分探索が適用できる.
"ぎりぎり単調増加を崩さない要素"はC++の場合lower_boundで簡単に見つけられる.

# 計算量

# 解答1

$O(NlogN)$

# 解答2

$O(N^2)$

# 解答1

// C++ 14
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <math.h>

#define ll long long
#define Int int
#define loop(x, start, end) for(Int x = start; x < end; x++)
#define loopdown(x, start, end) for(int x = start; x > end; x--)
#define rep(n) for(int x = 0; x < n; x++)
#define span(a,x,y) a.begin()+x,a.begin()+y
#define span_all(a) a.begin(),a.end()
#define len(x) (x.size())
#define last(x) (*(x.end()-1))

using namespace std;

#define N_MAX 100001

Int N;
vector<Int> A(N_MAX, -1);
vector<Int> L;

Int lis() {
  L.push_back(A[0]); // base case
  loop(n,1,N) { // general cases
    if (last(L) < A[n]) L.push_back(A[n]);
    else *lower_bound(span_all(L), A[n]) = A[n];
  }
  return len(L);
}

int main(void) {
  cin >> N;
  loop(i,0,N) cin >> A[i];
  cout << lis() << endl;
}

# 解答2

こちらのアルゴリズムに利点は無いので使用しないが、後のアイデアのために残しておく.

// C++ 14
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <math.h>

#define ll long long
#define Int int
#define loop(x, start, end) for(Int x = start; x < end; x++)
#define loopdown(x, start, end) for(int x = start; x > end; x--)
#define rep(n) for(int x = 0; x < n; x++)
#define span(a,x,y) a.begin()+x,a.begin()+y
#define span_all(a) a.begin(),a.end()
#define len(x) (x.size())
#define last(x) (*(x.end()-1))

using namespace std;

#define N_MAX 10001

Int N;
vector<Int> A(N_MAX, -1);
vector<Int> L(N_MAX, 0);

Int solve() {
  Int k, max_ = 0;
  loop(n,1,N+1) {
    k = 0;
    loop(l,0,n) {
      if (A[l] < A[n] && L[k] < L[l]) {
        k = l;
      }
    }

    L[n] = L[k] + 1;
    if (L[n] > max_) max_ = L[n];
  }

  return max_;
}

int main(void) {
  cin >> N;
  loop(i,0,N) cin >> A[i];
  cout << solve() << endl;
}