이전의 반도체 설계 문제와 동일하게 최장 증가 수열을 구하는 문제다.

2020년 4원 7일 포스트 수정

저 문제 풀 때는 dp가 뭔지도 몰랐다.
이번엔 동적 계획법으로 풀어봤다.
dp[i]에 arr[i]이전의 값들을 비교하며 arr[i]보다 작은 값이 있다면 그 때의 dp[]에 담겨있는 값 + 1을 dp[i]에 넣는다. arr[i]이전의 모든 수에 위 과정을 반복했을 때 가장 큰 수가 dp[i]가 된다.
마지막으로 dp[]에 담겨있는 값 중 가장 큰 값이 최장증가수열의 길이가 된다.

뭔가 했는데 알고리즘 분류를 보니 LIS라고 한다.

lower_bound로 최장증가수열을 구현하는 방식을 봤는데 실제로 유효한 수열을 구하진 않았다.

그런데 이 문제는 수열을 구하는 게 아니라 수열의 길이만 구하면 되므로 최대한 생략하고 수열의 길이만 구하도록 바꿨다.