최대 부분 증가수열(LIS) - python

<문제>

N개의 자연수로 이루어진 수열이 주어졌을 때, 그 중에서 가장 길게 증가하는(작은 수에서 큰 수로) 원소들의 집합을 찾는 프로그램을 작성하라. 예를 들어, 원소가 2, 7, 5, 8, 6, 4, 7, 12, 3 이면 가장 길게 증가하도록 원소들을 차례대로 뽑아내면 2, 5, 6, 7, 12를 뽑아내어 길 이가 5인 최대 부분 증가수열을 만들 수 있다.

▣ 입력설명
첫째 줄은 입력되는 데이터의 수 N(2≤N≤1,000, 자연수)를 의미하고, 둘째 줄은 N개의 입력데이터들이 주어진다.

 

▣ 출력설명
첫 번째 줄에 부분증가수열의 최대 길이를 출력한다.

 

▣ 입력예제 1
8

5 3 7 8 6 2 9 4 

 

▣ 출력예제 1

4

 

<풀이>

이 문제 같은 경우에는 LIS라고도 불리는 유명한 문제이다.

이 문제 같은 경우 입력에제에서 Bottom-up 방식으로 생각해서 문제를 풀었다.

첫번째인 5만 있을때, 5,3 이 있을때 5,3,7이 있을때 등등 이런식으로 문제접근을 하면

첫번째인 경우 최대 길이는 5 하나밖에없으므로 1이다. 2번째인경우 5,3 이 안되므로 3밖에 되질 않아서 최대 길이는 1이다. 3번째인경우 5,7이 되고 3,7 이 되기에 최대길이는 앞에 2이다. 즉 앞에 되는 값에 해당되는 값을 붙이면 된다. (물론 그 값이 그 전값보다 커야지 붙일 수 있다) 즉 1부터시작해서 DP[0]=1이기때문에(입력 숫자가 1개밖에없으면 최대길이는 1이기때문)해당하는 값 전까지 그 값보다 작으면 가장 큰길이에 +1을해서 DP테이블에 저장하면된다.

(8일경우 그 전에 가장 긴 값이 7이고 길이는 2이므로 8과 같은 위치 DP테이블에 저장되는 값은 3이다 2는 모든 값이 2보다  크므로 길이는 1이다)

 이런식으로 문제를 풀면 가장 긴 부분증가수열의 최대 길이를 구할 수 있다.

 

<코드>

n = int(input())
L = list(map(int,input().split()))
DP = [0] * n
DP[0] = 1

for i in range(1,n):
    a = L[i] # 이 값이 증가수열에서 마지막일때
    # print("a값은",a)
    maxx = 0
    for j in range(1,i):
        if a > L[j]:
            if maxx < DP[j] :
                maxx = DP[j]
    DP[i] = maxx + 1
    # print(DP)
print(max(DP))

중간에 a > L[j]를 a <L[j] 라고 해서 print를 찍어봤다.. 조심조심