- 문제 (11053번) : Longest Increasing Sequence
- LIS : Longest Increasing Sequence 로 증가하는 부분 수열 중 가장 긴 길이
- 즉, 증가하는 부분 수열 중 가장 긴 수열의 길이를 출력
- 입력 및 출력
[입력]
- 첫째줄에 수열의 크기를 입력
- 둘째줄에 수열을 구성하는 숫자 입력
[출력]
- 입력받은 수열의 증가하는 부분 수열 중 가장 긴 수열의 길이 출력
- 문제 풀이
- 수열의 처음부터 scan하면서 수열의 i번째 값 a[i]가 LIS에 포함되면 i-1번째까지의 LIS에 +1이 i번째까지의 LIS가 된다.
- 수열의 처음부터 scan하면서 수열의 i번째 값 a[i]가 LIS에 포함되지않으면 i번째의 LIS와 i-1번째까지의 LIS와 동일하다.
즉 다음과 같은 recurrence relation이 성립하게 된다.
- 이러한 recurrence relation을 코드로 작성하면 다음과 같다.
- 최종 코드
