백준 11053: 가장 긴 증가하는 부분 수열 (Python)

 

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

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

 

예제) n=6, A=[10, 20, 10, 30, 20, 50] -> 길이 4

처음에 리스트 초기화 d=[1, 1, 1, 1, 1, 1]

for문을 돌면서 차례대로 각 인덱스까지의 입력받은 배열 값을 비교해서 더 크면 최댓값 +1

 

1.

10	20	10	30	20	50
1	1	1	1	1	1

2. 10 < 20 이므로 d[1] = max(d[0]) + 1

10	20	10	30	20	50
1	2	1	1	1	1

3. 10 < 30 이므로 d[3] = max(d[0], d[1], d[2]) + 1 = d[2] + 1

10	20	10	30	20	50
1	2	1	3	1	1

4. 같은 방법으로 ~~ 하면 이런 배열이 완성된다

10	20	10	30	20	50
1	2	1	3	2	4

 

최종값은 최댓값 출력하기!

 

n = int(input())
a = list(map(int, input().split()))

d = [1] * n

for i in range(1, n):
    for j in range(i):
        if a[j] < a[i]:
            d[i] = max(d[i], d[j] + 1)

print(max(d))