1912)연속합

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

정답률이 보여주듯이 완전 어려운 문제였다.

주어진 예제나 여러 가지 반례는 통과시킬 수 있게 코드를 짰지만 결국 틀렸다.

질문 게시판에 들어가서 힌트를 얻고서야 풀 수 있었는데

완전 심플하고 신박한 방법이라 복습겸 써본다.

1.sum을 0으로 초기화한다.

2.값 하나를 읽어 sum에 더한다.

3-1.값 하나를 더한 sum이 0보다 크면, sum과 maxSum 중 더 큰 것을 maxSum에 저장한다. 

3-2.0보다 작으면 sum을 0으로 초기화한다.

4.수열이 끝날 때까지 2~3을 반복한 후 maxSum을 출력한다.

이렇게 하면 음수만 입력되는 경우를 제외한 모든 경우에 최대의 연속합을 구할 수 있다.

왜 그럴까?

sum은 계속 값을 더해가며 양수인 연속합을 갱신하는데 이 중 최대인 것을 maxSum이 저장하기 때문이다.

#include<stdio.h>
#define MAX(A,B) (A>B)?A:B
#define MIN_NEGATIVE -1001
 
int main() {
    int N;
    int value;
    int cntNegative = 0;
    int maxNegative = MIN_NEGATIVE;
    int sum = 0;
    int maxSum = 0;
 
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++) {
        scanf("%d", &value);
        if (value < 0) {
            maxNegative = MAX(value, maxNegative);
            cntNegative++;
        }
        
        sum += value;
        if (sum < 0) sum = 0;
        else maxSum = MAX(sum, maxSum);
    }
 
    if (cntNegative == N) printf("%d\n",maxNegative);
    else printf("%d\n",maxSum);
 
    system("pause");
    return 0;
}