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

문제📖

풀이🙏

• 이 알고리즘은 코딩 시 자주 등장하는 알고리즘이므로 외우도록 한다.
• dp 리스트는 해당 인덱스에서 증가하는 부분 수열의 길이를 저장한다.
• data의 값이 이전 값보다 클 경우 dp[i] = max(dp[i], dp[j]+1)를 통해 가장 긴 증가하는 부분 수열을 찾는다.

코드💻

n = int(input())
data = list(map(int, input().split()))
dp = [1] * (n+1)

for i in range(len(data)):
    for j in range(i):
        if data[j] < data[i]:
            dp[i] = max(dp[i], dp[j]+1)

print(max(dp))