[백준][Python][11053][DP]가장 긴 증가하는 부분 수열

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

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

DP 문제 중에 유명한 문제다.

Longest Increasing Subsequence LIS라는 문제다.

 

이 문제는 DP로 풀면  O(n^2) 가 나오고, binary search 등을 이용하면 O(nlogn)까지 줄일 수 있다고 한다.

물론 난 안줄인다. ㅎㅎ

 

dp 배열을 만들고, 다음과 같은 순서로 푼다

1. 0 ~ n-1  k 동안
   1. dp [i]를 1로 하고
   2. 0 ~ k-1 인 i 중에서 line [i] < line [k] , 즉 k 번째보다 작은 값을 보면
      1. dp [k], dp [i]+1 중에서 큰 값을 선택한다.
2. DP 배열중에 가장 큰 값을 고른다.

import sys

n = int(sys.stdin.readline())

line = [int(i) for i in sys.stdin.readline().rstrip().split()]

dp = [0] * n

if n ==1:
    print(1)
    sys.exit()

for k in range(n):
    dp[k] = 1
    for i in range(k):
        if line[i]<line[k]:
            dp[k] = max(dp[k], dp[i]+1)

print(max(dp))