[ 백준 11053번 ] 가장 긴 증가하는 부분 수열(LIS) 파이썬

[백준 11053번 바로가기]

11053번: 가장 긴 증가하는 부분 수열

논리

1. 주어진 문자열을 seq라고 할 때 seq[i]까지의 lis[i]를 기록해놓는다
2. i < j 인 seq[j]로 끝나는 lis 길이를 알기 위해 이전까지의 lis[i](i < j)를 참고한다
3. 이때, seq[i] < seq[j]라면 lis[j] = max(lis[j], lis[i]+1)로 계속 갱신한다

코드

import sys


def LIS():

    # inputs
    N = int(sys.stdin.readline())
    seq = list(map(int, sys.stdin.readline().split()))

    lis = [1] * N     # table[i]: series[i]로 끝나는 LIS 길이
    for i in range(N):
        for j in range(i):
            if seq[j] < seq[i]:
                lis[i] = max(lis[i], lis[j] + 1)

    print(max(lis))
    return


LIS()