최장 증가 부분 수열 (longest increasing subsequence)

최장 증가 부분 수열이란?

원소가 n개인 배열의 일부 원소를 골라내 만든 부분 수열 중에서(상대적인 순서는 유지) 길이가 최대인 수열을 의미한다.

ex) {4, 2, 3, 1, 6, 5}이라면? {2, 3, 6}이 된다.

---

가장 기본적인 해결 방안은 dynamic programming을 사용하는 것이다.

dp[i] : i까지 인덱스 중 가장 긴 수열의 길이

dp = [1] * n for i in range(n):     for j in range(i):         if ls[j] < ls[i]:             dp[i] = max(dp[i], dp[j] + 1)              print(max(dp))

# ls는 수열이 저장된 list임

# dp[i]는 i까지 인덱스 중 가장 긴 수열의 길이이기 때문에 j는 i보다 작아야 하고(배열의 순서) ls[j] 또한 ls[i]보다 작을 때 dp[i] = max(dp[i], dp[j] + 1)이 된다. max(dp[i], dp[j] + 1)을 하는 이유는 예를 들어 4번째 index일 때, 0~3까지 비교를 해야 하기 때문에 값이 중간에 1에서 다른 값으로 갱신이 될 수 있기 때문이다.

 

10 20 10 30 20 50를 보자

0	1	2	3	4	5
1	2	1	3	2	4

0 번째는 자기보다 작은 index가 없어서 1이 된다.

1 번째는 10보다 커서 2가 된다.

2 번째는 자기보다 작은 값이 없어서 1이 된다.

3 번째는 0 번째와 비교 후, dp[0] + 1한 값인 2가 되고, 그다음 1 번째인 2와 비교해 max(2, 3)을 해서 3이 된다.

4 번째는 0 번째와 비교 후, 2가 되고 그다음 2번째인 10과 비교해 (2, 2)가 돼서 2가 된다.

5 번째는 0 번째 -> 2, 1 번째 -> 3, 2 번째 -> 3, 3 번째 -> 4, 4번째 -> 4가 된다.