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

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

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

로직 구현 순서

1.입력값 받는 로직부분도 생각을 해야한다.

dp의 리스트를 1로 초기화 한 이유는 증가하는 수열의 값을 누적해서 더해주어야 하는데 만약 0으로 초기화 되면 1,2 의 경우 1이 가지고 있는 dp의 값은 0 이기 때문에 2까지 증가하는 수열의 최댓값은 1이된다. 1로 초기화 한 경우 1의 dp값이 1이기 때문에 수열의 최댓값이 2가 될 수 있다

dp = [1] * n

2.그 다음값과의 관계를 살펴야 한다.
다음값이 더 크면 증가하는 값이기 때문에 +1을 해주어야 하기 때문이다. 현재값과 다음값을 비교하기 위해 이중 for문을 사용한다. 현재수와 다음수의 크기를 비교하기 위해 입력한 수가 들어가 있는 n_list의 현재값과 다음값을 비교한다. 이때 j의 범위를 i로 두게 되면 i=2일경우 인덱스 i=0, i=1에 존재하는 수와 비교가 된다. 이때 i=0의 수는 없는것과 마찬가지므로 전의 값과 비교할 수 있게 된다.

이후 현재 dp[i] = 1 의 값과 dp[j] + 1(이전값에서 +1을 해주어야한다. 조건에서 이미 증가가 된것을 알기 때문에 누적시켜주어야 한다.) 을 더한 값 중에 max값을 구해주면 된다

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

(음,, 사실 max를 붙여주어야 하는지는 100% 이해하지는 못했다.. dp[j] + 1 이 무조건 클 줄 알았는데 아니다… 아시는 분…?)