[백준] 13398. 연속합 2

# 문제 설명

n개의 정수로 이루어진 임의의 수열이 주어질 때, 이 중 연속된 몇 개의 수를 선택하여 구할 수 있는 합 중 가장 큰 합을 구하려고 한다.

수는 한 개 이상 선택해야 하며, 수열에서 수를 하나 제거할 수 있다. (또한 제거하지 않아도 된다.)

 

# 입출력 예시

입력	출력
10 10 -4 3 1 5 6 -35 12 21 -1	54

 

# 내 풀이

n = int(input())
li = list(map(int, input().split(' ')))
li.remove(min(li)) # ?

dp = max(max(li), sum(li))
for i in range(2, n):
    for j in range(n-i+1):
        dp = max(dp, sum(li[i:j+i]))
print(dp)

-> 시간 초과 && 제거하지 않았을 때 고려 X

 

# 정답 : O(n) 풀이

n = int(input())
li = list(map(int, input().split(' ')))
dp = [[0]*n for _ in range(2)]

dp[0][0] = li[0]
if n < 2:
	print(dp[0][0])
else:
    answer = 0
    for i in range(1, n):
        dp[0][i] = max(dp[0][i-1] + li[i], li[i]) # 특정 원소를 제거하지 않는 경우
        dp[1][i] = max(dp[0][i-1], dp[1][i-1] + li[i]) # 특정 원소를 제거하는 경우
        answer = max(answer, dp[0][i], dp[1][i])
    print(answer)

 

# 핵심 포인트

• 특정 원소를 제거한 경우와 그렇지 않은 경우 모두 고려해야 할 대상이기 때문에, 병렬적으로 처리해주어야 한다.
• DP로 꾸준히 이전 노드까지의 연속하는 최대 합을 저장한다.
• answer에는 특정 원소를 제거한 경우나 그렇지 않은 경우 또는 이전 answer 중 최적의 값으로 계속 업데이트 해준다.