최장증가수열 백준 2352번 반도체 설계 알고리즘 문제

max_increase_seq.py

N = int(input())
input_num = input().split(" ")
input_num = [int(num) for num in input_num]

def change(result_list, num):
    for i in range(len(result_list)-1,-1,-1):
        if(result_list[i] > num):
            idx = i
        else:
            break
    result_list[idx] = num
    return result_list

result_list = [input_num[0]]

for i in range(1, len(input_num)):
    if(result_list[-1] < input_num[i]):
        result_list.append(input_num[i])
    else:
        result_list = change(result_list, input_num[i])


print(len(result_list))

## 6
## 4 2 6 3 1 5
## result : 3

## 참고 : 최장증가수열 https://codedoc.tistory.com/414
## 백준문제 2352번 반도체 설계 : https://www.acmicpc.net/problem/2352