[백준] 11053번-(Python 파이썬) - DP

문제링크:https://www.acmicpc.net/problem/11053

이번 문제는 가장 긴 증가하는 부분 수열 구하기이다.
LIS(longest incleasing subsequence)라고 불리기도 하는데 dp로 풀 수 있는
보편적인 문제유형 중 하나이다.

각 수 마다 자신보다 앞에있는 수이면서 작은 숫자들 중 가장 큰 길이를 구해서
그 길이에 + 1 만 해주면 답이 나오는 간단한 문제엿다.

import sys
input = sys.stdin.readline

n = int(input())

sequence = list(map(int, input().split()))
dp = [0 for _ in range(n)]

for i in range(n):
  for j in range(i):
    if sequence[i] > sequence[j] and dp[i] < dp[j]:
      dp[i] = dp[j]
  dp[i] += 1
  
print(max(dp))