DP (1) 최장 증가 부분 수열

                                    ⚠️ 처음에 문제를 잘못 읽어서 등차수열로 풀었음

👉 이후 수정하여 다음과 같은 코드로 작성

                                    import sys

n = sys.stdin.readline()
A = list(map(int, sys.stdin.readline().rstrip().split(" ")))

# 정렬 쓰면 안된다.

seq_max_len = -1
for i in range(len(A)):
    pivot = A[i]
    tmp_len = 0
    for j in range(i + 1, len(A)):
        if A[j] > pivot:
            tmp_len += 1
            pivot = A[j]
    seq_max_len = max(seq_max_len, tmp_len + 1)

print(seq_max_len)

                                    10 20 30 22 23 24

✍️ 해당 코드를 적용하면
10 20 30  max = 3

🚀 실제 구현해야 하는 것
10 20 22 23 24 max = 5

                                    ✍️ dp[i] = 끝이 A[i]인 최장 증가 부분 수열의 길이로 정의

1. dp[i] 정의에 의해서 A[i]의 이전의 값이 A[i] 보다 작은 경우에만 길이가 증가.
2. dp[i]는
    dp[i - 1, i - 2 ...] 의 값이 dp[i] 보다 작고,
    해당 idx의 A[i - 1, i - 2, ...] 는 A[i] 보다 작아야한다.

                                    import sys

n = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().rstrip().split(" ")))

# 정렬 쓰면 안된다.

seq_max_len = -1
dp = [1] * n

for i in range(1, len(A)):
    num = A[i]

    back = i - 1
    max_dp_back = 0
    while back >= 0:
        if A[back] < num:
            max_dp_back = max(dp[back], max_dp_back)

        back -= 1

    dp[i] = 1 + max_dp_back
print(max(dp))