[BOJ] 11053번 - 가장 긴 증가하는 부분 수열

---

문제설명

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

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

사고과정

• 이전에 이코테 문제에서 풀어본 병사 배치하기 문제를 통해서 LIS(가장 긴 증가하는 부분 수열) 알고리즘에 대해 배웠었다. git 팀 노트에 적어놓긴 했었지만 다시 회상할 겸 소스코드를 보지 않고 직접 머릿속으로 구현하려 했다.
• LIS 알고리즘 개념은 여기를 참고하자.

풀이

a = int(input())
array = list(map(int, input().split()))
dp = [1] * a

for i in range(1, a):
    for j in range(i-1, -1, -1):
        if array[i] > array[j]:
            dp[i] = max(dp[i], dp[j] + 1)

print(max(dp))