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

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

문제풀이
N <= 1000 (N은 자연수)의 조건을 보고 시간복잡도상 2중 for문을 사용할 수 있는 것을 알았다. 
경우의 수가 너무 많기에  DP로 푸는 문제임을 직관적으로 알 수 있었고 인덱스가 증가함에 따라 값이 증가해서 부분수열의 길이가 늘어나야한다면 현재까지의 부분수열의 길이와 이전 상황들에 대한 부분수열의 길이를 비교해서 더 큰 값을 현재까지의 부분수열의 길이로 정할 수 있다.
따라서 점화식은 아래와 같다.

if A[j] < A[i]:
    dp[i] = max(dp[i], dp[j] + 1)

---

Code

from sys import stdin

input = stdin.readline


def solve():
    N = int(input())
    A = list(map(int, input().split()))
    dp = [1] * N
    for i in range(1, N):
        for j in range(i):
            if A[j] < A[i]:
                dp[i] = max(dp[i], dp[j] + 1)

    print(max(dp))


solve()