[백준] 11055 - 가장 큰 증가 부분 수열 (DP)

https://www.acmicpc.net/problem/11055

11055번: 가장 큰 증가 부분 수열

 

난이도 : 하

DP 기본 문제

 

import sys

n = int(sys.stdin.readline())
a = list(map(int,sys.stdin.readline().split()))


dp = [0]*n 
for i in range(n) :
  dp[i] = a[i] # 자기자신만 수열인 경우

for i in range(n):
  for j in range(i):
    if a[i] > a[j]:
      dp[i] = max(dp[j]+ a[i],dp[i])

print(max(dp))