백준 1912번 C++ 연속합

연속합

https://www.acmicpc.net/problem/1912

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

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

생각하는 과정

이 문제에서 생각해 볼 수 있는 케이스는 연속일 때만을 고려하므로, 두 가지다.

i번째를 선택한다는 가정하에

1) 연속이 아닐때(i-1번째를 선택하지 않을 때) -> dp[i] 선택(자기 자신만을 가지고 감)

2) 연속일 때(i-1번째를 선택할 때) -> dp[i-1]+series[i] 선택(자기 자신보다 그 전의 연속합에 자기 자신을 더한 것이 더 큼)

예제에서 생각해보자. 연속합이 최대여야 한다.

10, -4, 3, 1, 5, 6, -35, 12, 21, -1

0번째에서 최대합은 10 하나뿐이므로 10이다.

1번째에서 최대합은 -4<10-4이므로 6이다. 

2번째에서 최대합은 3<6+3이므로 9이다.

3번째에서 최대합은 1<9+1이므로 10이다.

4번째에서 최대합은 5<10+5이므로 15이다.

5번째에서 최대합은 6<15+6이므로 21이다.

6번째에서 최대합은 -35<21-35이므로 -14이다.

7번째에서 최대합은 12>12-14이므로 12이다. <-끊기는 지점

8번째에서 최대합은 21<12+21이므로 33이다.

9번째에서 최대합은 -1<33-1이므로 32이다.

마지막으로 이 중에서 최대를 고르면 33이다.

이 문제에서 0번째 인덱스를 고려해주지 않아도 되는 이유는 0번째 인덱스를 선택하든 말든 중간이 끊기지 않고

수열의 최대합을 구하는 게 아니라 '연속하는' 최대합을 구하는 것이기 때문이다.

0번째 인덱스를 선택하는 것보다 어느 지점에서 어느 지점까지를 연속합으로 택하느냐가 총합을 결정짓는다. 

코드

#include <iostream>
#define MAX 100001
using namespace std;
int series[MAX], dp[MAX]={0,};
int main() {
    int n, i;
    cin>>n;
    for(i=0; i<n; i++) {
        cin>>series[i];
        dp[i]=series[i];
    }
    int maxSum=dp[0];
    for(i=1; i<n; i++) {
        dp[i]=max(dp[i], dp[i-1]+series[i]);
        if(dp[i]>maxSum) {
            maxSum=dp[i];
        }
    }
    cout<<maxSum<<endl;
    return 0;
}

결과

아마 생각하고 풀었으면 틀렸을 것이다...

꾸준하게 하자