[白俊]11053号-(Python Python)-DP

質問リンク:https://www.acmicpc.net/problem/11053


この問題は最も長い増分部分の数列を求めることです.
LIS(最長increating subsequence)とも呼ばれる
普遍的な問題のタイプの一つです.
それぞれの数は自分より前の数で、小さな数字の中で最大の長さを求めます.
これは簡単な問題で、長さに+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))