이번 문제는 문제를 이해하는데에 시간이 조금 걸렸던 문제였다. 간단하게 해석하면 주어진 수열에서 사이사이에 원하는 수를 뺄 수 있고 원하는대로 뺀 뒤에 남은 증가 부분 수열 중에서 합이 가장 큰 것을 출력하는 문제이다.

• n과 수열 arr을 입력받는다.
• arr의 각 자리에서의 증가 부분 수열 합을 저장할 dp배열을 선언한다.
• 이중 for문을 돌린다.
  -> 바깥 for문은 0부터 n-1까지, 안쪽 for문은 0부터 i-1까지 반복한다.
  -> 이때 안쪽 for문에서 arr[i]가 arr[j]보다 클 경우(증가 부분 수열일 경우) dp[i]를 결정한다. dp[i]는 dp[i]와 dp[j]+arr[i]중 더 큰 것으로 취한다.
• answer에 dp배열에서 가장 큰 수를 저장한다.
• answer를 출력한다.

Code

n = int(input())
arr = list(map(int, input().split()))
dp = [x for x in arr]
for i in range(n):
    for j in range(i):
        if arr[i] > arr[j]:
            dp[i] = max(dp[i], dp[j]+arr[i])
answer = max(dp)
print(answer)