最長増加部分列の長さ

最長増加部分列の長さを求める。

コードを読むとイメージがつかめる。

using namespace std;
long long dp[100001];
long long a[100001];
int main()
{
  int n;
     
  scanf("%d", &n);
  fill(dp, dp+n, 10e8);
  for(int i=0; i<n; i++)
    scanf("%Ld", &a[i]);
     
  for(int i=0; i<n; i++)
    *lower_bound(dp, dp+n, a[i]) = a[i];
     
  printf("%Ld\n", lower_bound(dp, dp+n, 10e8) - dp);
     
  return 0;
}

解説は以下

1. 最長増加部分列 | 動的計画法 | Aizu Online Judge
2. 蟻本 P.65