[백준] 11053번 가장 긴 증가하는 부분 수열 C++ 코드

코드

#include <iostream>

using namespace std;
int n, a[1003], cnt[1003],res;
int main() {
  cin >> n;
  fill(cnt, cnt + 1003, 1);
  for(int i = 0; i < n; i++) {
      cin >> a[i];
  }
  for(int i = 0; i < n; i++) {
    for(int j = 0; j < i; j++) {
      if(a[j] < a[i] && cnt[i] < cnt[j] + 1) {
        cnt[i] = cnt[j] + 1;
      }
    }
    res = max(res, cnt[i]);
  }
  cout << res << '\n';
  return 0;
}

O(N^2)으로 가장 긴 증가하는 부분 수열(LIS, longest increasing subsequence)를 구하는 문제.