가장 긴 증가하는 부분 수열

이 문제는 가장 길게 증가하는 부분 수열을 구하는 것이다.
A = {10, 20, 10, 30, 20, 50}인 경우
A 배열중 10, 20, 30, 50이 가장 긴 부분 수열이고 길이가 4이다.

여기서 나는 dp[5]가 4가 나오도록 설계를 해야겠다 생각했다.
그러면서 dp는 다음과 같이 설정을 했다.

dp[i] = i번째 인덱스에서 가질 수 있는 최대 부분 수열의 개수를 가진 원소

즉, 위와 같이 정의를 하면 dp[i]는 i번째 위치에서 최대 부분 수열의 개수를 가질 수 있도록 설계해야한다.
해당 문제는 코드를 먼저 보여주고, 설명을 작성하려한다.

import sys

N = int(sys.stdin.readline().strip())
array = list(map(int, sys.stdin.readline().split()))
dp = [1 for _ in range(N)]

for i in range(1, N):
    for j in range(i):  # i 인덱스 안에서 비교하는 이유는 j부터 i까지 비교하면서 dp[i]를 확실히 정하기 위해서
        if array[i] > array[j]:  # array[i]가 array[j]보다 큰 경우 부분 수열이기 때문에 dp[i]를 최신화 한다
            dp[i] = max(dp[i], dp[j] + 1)  # dp[j]는 이미 j 인덱스까지 이미 확정된 오름차순의 숫자의 수이므로 여기에 1을 더한 것과 기존의 dp[i]와 비교한다.

print(max(dp))

위의 코드에서 2중 for문중 j에 대해서 i전까지 검사하는 이유는 특정 배열 요소까지 검사하기 위해서이다.
예를 들어 설명을 하자면 위의 예제중 3번째 인덱스인 30을 비교하려면, 0~2번째 인덱스와 비교를 해야한다.

첫번째 for문이 수행이 되면, 그때 마다 dp배열이 순차적으로 확정되는 로직을 가져갔다.
두번째 for문은 dp배열을 확정짓는 로직을 가져갔다.
array[i] > array[j]인 경우, dp[i]와 dp[j]+1을 비교해서 넣어줘야 한다.
기존에 있는 dp[i]가 더 클 수 있기 때문이고, dp[j]+1을 하는 이유는 새로운 오름차순의 숫자가 추가되었기 때문이다.

그러고 난 뒤, dp배열중 가장 큰 값을 추출해서 보여주면 된다.