[백준] 11055번 가장 큰 증가 부분 수열(python)(dp)

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

 

1. 난이도 실버2 (🥈) 

 

2. 문제 해결 방법

 

가장 긴 증가하는 부분 수열과 비슷한 문제다.

 

증가하고 있을 경우 max(본인이 가지고 있는 누적합, 그 전 원소의 누적합 + 본인의 값)를 출력하면 되고,

 

감소하고 있을 경우 max(본인이 가지고 있는 누적합, 본인의 값)을 출력하면 된다. 

 

 

감소하고 있을 경우를 고려하지 않고 제출해서 2트만에 맞았다.

 

3. 내가 작성한 코드

n = int(input())

num = list(map(int, input().split()))

dp = [0] * n
dp[0] = num[0]

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

print(max(dp))