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

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

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

코드

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

for i in range(n): 
    for j in range(i): 
        if arr[i] > arr[j]:
            dp[i] = max(dp[j]+1,dp[i])

print(max(dp))

풀이

• 다이나믹 프로그래밍으로 i번째 인덱스의 값을 가장 긴 증가하는 부분 수열의 길이를 계속 갱신한다.
• dp[i]를 구하기 위해서, 2중 for문으로 0부터 i까지 j라고 하면, arr[i] > arr[j]인 경우 j까지의 가장 긴 증가하는 부분 수열의 길이,즉 dp[j]의 값에서 1을 더한 값과 기존의 dp[i]값중 더 긴(최댓값)을 dp[i]에 갱신하면 된다.