#135 백준 파이썬 [11053] 가장 긴 증가하는 부분 수열 - LIS

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

 

 

#Solution

다음과 같은 알고리즘을 따른다.

1) i 번째는 0부터 i-1 까지 수열(j)을 검사하면서 넘어간다.

2) 이전 수열들 중 마지막 숫자가 나보다 작은지 비교한다. (조건 1)

2-1) 작다면 해당 수열을 추가해주고 나 자신을 추가한다.

3) j for문을 돌리던 중 2)에 해당하지만, 수열의 길이가 더 길 경우 result[i]를 갱신해준다.

4) 반복한다.

5) 적절한 result[i]를 찾지 못했을 경우, 자신이 최소값이므로 자기 자신을 추가해준다.

 

6) result안 수열들 중 길이가 가장 max인 것의 길이를 출력한다.

 

A = int(input())
A_list = list(map(int, input().split()))
result = [[] for _ in range(A)]

for i in range(A):
    if i == 0:
        result[i].append(A_list[i])
    else:
        for j in range(0, i):
            if result[j][-1] < A_list[i]: #이전 수열의 마지막 숫자가 나보다 작은가?
                if len(result[i]) - 1 < len(result[j]): #수열의 길이가 현재값보다 작은가?
                    result[i] = result[j] + [A_list[i]]
        if not result[i]:
            result[i].append(A_list[i]) #자신이 지금까지 최소값일 경우

answer = 0
for i in range(A):
    answer = max(answer, len(result[i]))
print(answer)