python 백준 11053 가장 긴 증가하는 부분 수열

• dp 활용
  • index : index번호가 수열의 마지막 번호 일 때 될 수 있는 수열의 최장 길이
  • 기본값 1 : 자기 자신 하나로 이루어진 수열은 최소 존재해서 1로 설정
• solve 함수
  • 앞에서 부터 차근차근 진행(i는 0부터 N까지)
  • 기존의 값들과 비교 (j는 0부터 i까지)
  • A[j] < A[i] 이면 그 숫자 뒤에 연결하여 수열을 만들 수 있으므로
    • 이 경우 최대값이 갱신 되면 갱신

def solve():
    for i in range(N):
        for j in range(0,i):
            if A[j] < A[i]:
                dp[i] = max(dp[i],dp[j]+1)

N = int(input())
A = list(map(int,input().split()))
dp = [1]*N
solve()
print(max(dp))