[백준] No.13398 - 연속합2 (C++)
문제
13398번: 연속합 2
첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.
www.acmicpc.net
풀이
누적 합과도 연관된 DP문제.
연속합1 문제의 경우 해당 숫자를 합에 더하거나 해당 숫자에서 다시 연속 합 계산을 시작하는 두 경우를 비교하여 O(n)시간에 가장 큰 연속합을 구할 수 있다.
본 문제에서는 수열 중에서 한 숫자를 제외하거나 하지 않는 연속합들 중 최댓값을 찾아야 한다.
연속합1과는 다르게 2차원 배열 dp[100000][2]를 이용한다.
1. dp[i][0]에는 숫자가 제외되지 않은 경우를 저장한다.
i번째 수를 더한 경우(dp[i-1][0] + num)와 i번째부터 다시 시작하는 경우(num)을 비교하여 더 큰 수가 dp[i][0]이다.
dp[i][0] = max(dp[i-1][0] + temp_num, temp_num);
2. dp[i][0]에는 숫자가 제외된 경우를 저장한다.
i번째 수를 제외하여 연속합을 구하는 경우 dp[i-1][0]의 값을 그대로 가져온다.
제외하지 않는 경우, 이미 특정 수가 제외된 연속합의 최댓값 dp[i-1][1]에 i번째 수(num)을 더해준다.
dp[i][1] = max(dp[i-1][0], dp[i-1][1]+ temp_num);
최종적으로 1,2번 경우 중 더 큰 값을 max_num과 비교한다.
본 코드에서는 max_num은 for문에 포함되지 않는 dp[0][0]값으로 미리 초기화해 준다.