문제 링크: https://www.acmicpc.net/problem/11055

Thumbnail: Photo by Walls.io (Unsplash)

어제 풀었던 LIS 문제와 마찬가지이나, LIS의 길이가 아닌 원소 합을 기준으로 찾는 문제입니다.

풀이

LIS 이해하기

이 문제는 LIS의 DP 방식 풀이로 풀 수 있습니다! 관련 내용은 이전 글 참고해주세요~

DP 배열 채우기

이전에 LIS 배열을 채울 때, 원소가 증가하는지 비교한 뒤, dp 배열을 LIS의 길이로 갱신해주었습니다. 하지만, 이번 문제는 LIS의 길이가 아닌 원소의 합을 요구합니다. 따라서, dp 배열의 값을 LIS의 원소 합으로 갱신하도록 수정하면 됩니다.

전체 코드

input = open(0).readline
N = int(input().strip())
A = list(map(int, input().strip().split()))

dp = [A[i] for i in range(N)]
for i in range(N):
    for j in range(i + 1, N):
        if A[j] > A[i]:
            dp[j] = max(dp[j], dp[i] + A[j])

print(max(dp))