[BOJ/백준] 13398 연속합 2

N = int(input())

arr = list(map(int,input().split()))
minus_inf = -float('inf')
dp = [[minus_inf]*N for _ in range(2)]
dp[0][0] = arr[0]
for ind in range(1,N):
    dp[0][ind] = max(dp[0][ind-1]+arr[ind],arr[ind])
    dp[1][ind] = max(dp[0][ind-1],dp[1][ind-1]+arr[ind])

print(max(map(max,dp)))

DP 관련 문제이다. 점화식을 찾고, 그걸 표현하는데 오래걸렸다. 

 

기본 문제풀이 원리는 다음과 같다. 2개의 DP를 만들어

 

한쪽은 원래 그대로의 수열을 표현했을 때, 최대값을 저장해놓은 DP 배열

다른 한쪽은 수열 중 한 부분을 뺐을때, 최대값을 저장해놓는 DP 배열이다.

 

DP[flag][IDX] = flag가 0이면 계속해서 연속인 배열, 1이면, 배열 중 한 인덱스를 뺏을때의 배열을 나타낸다.

                     idx는 현재의 위치를 나타낸다.

 

먼저 원래 그대로 배열을 표현했을때 최대값이 될수 있는것은

 

현재 위치를 IDX라고 할시, DP[0][IDX] +arr[IDX]이나, arr[IDX] 중에 최대값이다. 계속 연속되는 합 같은경우 계속 이어져 오거나 현재위치부터 다시 시작하거나 둘중 하나이기 때문에 둘중 큰 값을 DP에 저장해놓는다.

 

그리고 배열 중 한 부분을 뺐을때 최대값이 될 수 있는것은

 

현재 IDX를 뺐을때와 현재 IDX는 포함하고 이전의 IDX 중 하나가 빠졌을때 둘 중 하나이다.

 

그러므로 점화식으로 나타내면 DP[1][IDX-1] + arr[IDX] , DP[0][IDX-1] 이다.

 

 

위와 같은 식으로 전체의 dp를 구한뒤 최대값을 출력해주면 된다.