BOJ 1912 연속합

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

1912번: 연속합

첫 번째 풀이

#include <cstdio>

int main() {
    int n;
    scanf("%d",&n);
    int  sum[n], max;
    
    for(int i=0;i<n;++i) {
        scanf("%d",&sum[i]);
        if(i>0)
            sum[i] += sum[i-1];
    }
    max = sum[0];
    
    for(int i=1;i<n;++i)
        for(int j=0;j<i;++j)
            if(max < sum[i]-sum[j])
                max = sum[i]-sum[j];
    printf("%d",max);
}

O(n^2) 알고리즘이다.

 

sum[i]는 다음과 같이 정의된다

sum[i]: 0~i까지의 누적 합

 

따라서 sum[i] - sum[j] -> j~i 까지 연속 합이고, 그 중에서 최대를 찾는다.

 

아슬아슬하게 통과할 줄 알았지만, 시간 초과로 오답이 나왔다.

두 번째 풀이

#include <cstdio>

int main() {
    int n;
    scanf("%d",&n);
    int  in[n], dp[n], max;
    for(int i=0;i<n;++i)
        scanf("%d",&in[i]);
        
    dp[0] = in[0];
    max = in[0];
    
    for(int i=1;i<n;++i) {
        if(dp[i-1] + in[i] > in[i]) dp[i] = dp[i-1] + in[i];
        else dp[i] = in[i];
        if(dp[i] > max) max = dp[i];
    }

    printf("%d",max);
}

O(n) 시간에 수행된다.

 

dp[i]를 다음과 같이 정의하자

dp[i]: i 까지의 연속합의 최대(local maximum)

 

위와 같이 정의할 때 점화식은 다음과 같다.

dp[i-1] + a[i]: i-1까지의 연속합과 a[i] 원소를 더한 값이 a[i] 원소보다 작거나 같으면

 i.e. 연속한 음수로 a[i]를 더하면 연속 합이 더 작아지기만 하는 경우 혹은 dp[i-1] = 0으로 더해도 의미가 없는 경우, i까지 연속합의 최대를 a[i]로 설정