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

풀이

dp 배열에 dp[i]를 마지막으로 하는 가장 긴 증가하는 부분 수열의 원소 개수를 저장한다.
이중 반복문에서 arr[i]가 arr[j]보다 클 때, dp[j] 값 역시 dp[i] 값보다 더 크다면 dp[i]를 dp[j]로 바꿔준다. j 반복문이 끝나고 dp[i] 값이 확정되었다면 부분 수열에 추가 되었으므로 1을 더해준다.

소스코드

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().strip().split()))
dp = [0 for i in range(n)]

for i in range(n):
    for j in range(i):
        if arr[j] < arr[i] and dp[i] < dp[j]:
            dp[i] = dp[j]
    dp[i] += 1

print(max(dp))