[백준] 11055 가장 큰 증가 부분 수열

문제

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

내 코드

n=int(input())
mlist=list(map(int, input().split()))

dp=[0]*n
dp[0]=mlist[0]  
for i in range(n):
    for j in range(i):
        if  mlist[i]>mlist[j]:
            dp[i]=max(dp[i], mlist[i]+dp[j])
        else:
            dp[i]=max(dp[i], mlist[i])

print(max(dp))

풀이

• 바깥 for문은 n만큼
• 안쪽 for문은 i만큼 돌기
• 만약 mlist[i]>mlist[j] 즉 뒤에 나오는 수가 더 크다면 dp[i]에 dp[i]에 원래 있던 수와 dp[i]에 mlist[i]를 더한 값 중 더 큰 값을 저장
• 만약 아니라면 dp[i]에는 dp[i]와 mlist[i] 중 더 큰 수 저장
• 가장 큰 수를 출력