lis알고리즘 (최고 증가 부분수열)

lis 알고리즘에 대해 정리하자면 이렇다.

lis의 문제상황은 이렇다.

주어진 수열이
4 2 5 8 4 11 15
이라할때 가장 큰 증가 부분 은
{2, 5, 8, 11, 15}가 되는데

lis알고리즘은 이런식으로 해결한다.
dp의 개념을 어느정도 적용하는데
이때 dp테이블은 1차원 리스트이며

점화식은 d[i] = d[j] + 1 if(array[j] < array[i]) 이때 (0 <= j <= i)

리스트의 각 index까지의 가장 긴 부분증가 수열의 길이가 된다.
예를들어 위의 수열에서는 dp 테이블은 이런식으로 완성될 것이다.

index	1	2	3	4	5	6	7
dp	1	1	2	3	2	4	5
array	4	2	5	8	4	11	15

따라서 가장긴 부분증가수열의 길이는 max(dp)인 5가 된다.

코드로 구현해보자면

#lis 알고리즘
#dp 점화식
#점화식은 d[i] = d[j] + 1 if(array[j] < array[i])  이때 (0 <= j <= i)

import sys
size = int(sys.stdin.readline().rstrip())

array = []
array = list(map(int, sys.stdin.readline().split()))

dp = [1] * (size + 1)

for i in range(size):
  for j in range(i):
    if array[j] < array[i]:
      dp[i] = max(dp[i], dp[j] + 1)
  

print(max(dp))