알고리즘매일매일

https://www.acmicpc.net/problem/11053

문제 제목 그대로 가장 긴 증가하는 부분 수열 LIS (Longest increasing Subsequence) 문제이다.

일반적으로 dp 식을 사용해서 풀 수 있다.

dp[i]는 수열의 i번째 값을 마지막으로 하는 가장 긴 증가하는 부분 수열이다.

dp[i]값을 구하기 위해서는 첫 번째 값부터 i-1번째 값( j )까지를 검사한다. -> 시간 복잡도는 n제곱이 된다

(먼저 dp배열은 자기 자신을 부분 수열로 하면 최소 길이가 1이므로 1로 초기화해준다)

1. j번 수열의 값이 i번 수열의 값보다 작고 (증가하는 수열이어야 하므로)

2. dp[j]값은 현재 dp[i]값보다 같거나 커야 한다(가장 긴 수열)

위의 조건을 만족한다면 dp[i] 는 dp[j] + 1 값을 가지게 된다(수열의 길이가 1 늘어남) 

문제에 나온 예시를 그림으로 보면 처음에 첫 번째 값(i가 0)인 10은 최대 길이가 1이므로 1인 상태로 다음 수열로 넘어간다.

수열의 다음 값(i가 1)은 20인데 앞의 값은 10 밖에 없다. 10은 20보다 작고 dp값도 같기 때문에 dp[i]값은 +1 된다.

그다음 값은 10인데 앞의 값들(10과 20) 중 10보다 작은 값이 없으므로 길이는 그대로 자기 자신인 1이 된다.

그리고 i는 증가해서 30 값을 가리킨다. 현재 i가 3이므로 0번부터 2(i-1) 번까지의 값을 보면 된다.

0번부터 2번까지의 값은 각각 10, 20, 10으로 모두 30보다 작다.

이중 dp배열의 가장 큰 값+1이 dp[i]값이 되므로 dp[1]값인 2에서 1을 더한 3이 dp[3]에 저장된다.

i값이 4가 되고 이제 j는 0부터 3까지의 값을 검사한다.

이 중 20보다 작은 값은 0번째와 2번째이다. 둘 다 10이고 dp의 값도 1로 현재 dp[i]와 같으므로 dp[i]는 dp[j]에 1을 더한 값인 2가 된다.

마지막 값인 50과 앞의 값들을 비교해보면 모두 50보다 작다. 그러므로 가장 큰 dp값인 dp[3] + 1 한 값인 4가 dp[5]에 저장된다.

마지막 값이 작은 값인 경우에는 마지막 위치에 최댓값이 저장되지 않을 수 있으므로 dp배열을 모두 검사해서 최댓값을 찾아야 한다.