개발 블로그

문제 링크 : www.acmicpc.net/problem/1912

문제

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

입력

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

접근 방법

처음에는 DP1[i]를 Arr[0]~Arr[i] 까지 고려했을 때 연속되는 수열의 최대 합을 저장하도록 구현했었다.즉 Arr[i-1] 부터 Arr[0] 까지 거꾸로 가면서 음수가 나오면 그 음수를 수열에 포함할 것인지 아닌지에 따라 경우를 나눠야했다.

아래 표에서 색칠한 부분을 생각해보자. 

i=6일 때, Arr[6] 이 -35로 음수이다. -35를 포함하지 않고 Arr[i] ~ Arr[5] 까지만 더한 21이 최대합을 가지는 수열이다. 이는 i=7일때도 같으며, i=8이 되는 순간 Arr[7] + Arr[8] 을 더한 33이 최대합이 된다. 

이 방법으로 구현했을 때, Arr[i]이 음수인 경우 그 음수만큼 상쇄시켜서 양수로 만들 수 있을 때 까지 Arr[i]을 거꾸로 탐색해가면서 수열에 포함해야할지 따져야 하는데 너무 복잡해져서 다시 DP2[i]를 구하는 방법으로 구현했다.

DP2[i]는 DP1[i] 과 달리 Arr[0]부터 Arr[i] 까지 고려했을 때 최대값을 담고 있지 않다. 그러나 DP2[i]를 채우면서 최대값(ans)을 따로 저장해준다면 

DP2[i]는 DP2[i-1]에다가 Arr[i] 을 계속 더해 나가는 방법이되, 더했는데도 현재 숫자인 Arr[i]보다 작으면 바로 Arr[i]이 원소 한개인 수열이 되도록 하는 것이다.  아래 예시를 들어봤다.

i = 1

10-4 vs -4 = 6

i=2

6+3 vs 3 = 9

i = 3

9+1 vs 10 = 10

i = 4

10+5 vs 5

i = 5

15+6 vs 6

i = 6

21-35 vs -35 = -14

i = 7

-14+12 vs 12 = 12

....

예시들을 아래 코드로 옮겼다.

        DP[i] = max(DP[i-1] + Arr[i], Arr[i]);
        ans = max(ans, DP[i]);

이 코드가 핵심이다. 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int Arr[100001] = {0};
int DP[100001] = {0};

int main(){
    
    
    int N;
    cin >> N;
    int ans;
        
    for(int i = 0; i<=N; i++){ cin >> Arr[i];}
    
    DP[0] = Arr[0];
    ans = Arr[0];
    for(int i = 1; i<N; i++){
        
        DP[i] = max(DP[i-1] + Arr[i], Arr[i]);
        ans = max(ans, DP[i]);
        
    }
    
    cout << ans;
    
    
    return 0;
}

참고 : Arr[i]의 최대 값은 1000이며, N 최대값은 100,000 이다. 즉 Arr[0] ~ Arr[100,000] 에 모두 1000이 저장되어도 int 형의 범위를 넘지 않는다. 그래서 Dp[]는 int 형으로 해도 괜찮다.