1912번 연속합 BOJ 백준 C언어

문제

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

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

입력

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

출력

첫째 줄에 답을 출력한다.

구현

연속합 문제에서 가장 중요한 점은 음수를 받았을 경우에 무조건 연속합이 작아지지 않는 경우가 있다는 것이다. 따라서 sum값을 항상 따로 저장해주고 0보다 작아질 경우 초기화시켜서 새로 들어온 양수 값을 넣어줘야 한다.

실수로 생길 수 있는 반례들은

5 -1 -2 -3 -4 -5 // 5 -5 -4 -3 -2 -1

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

max 10 10 10 10 15 21 21 21 33 33

sum 10 6 9 10 15 21 -14 12(-2) 33 32

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#define _CRT_SECURE_NO_WARNINGS

int compare(int a, int b) {
    return (a > b) ? a : b;
}

int main(void) {
    int num, i, max = -1000, sum = 0;
    int arr[100001] = { 0 };

    scanf("%d", &num);

    for (i = 1; i <= num; i++) {
        scanf("%d", &arr[i]);
        if (arr[i] > 0) { //해당 값이 양수일 경우
            if (sum < 0) { //이전 값까지의 합이 음수일 경우
                sum = 0; //더해온 값을 초기화하고
                sum = sum + arr[i]; //새로 저장한다.
            }
            else { //이전 값까지의 합이 양수일 경우
                sum = sum + arr[i]; //계속 더해준다.
            }
            max = compare(max, sum); //if(sum<0)일 경우 새로 더한값이 클수 있기에 비교해준다.
        }
        else { //해당 값이 음수일 경우
            if (sum <= 0) { //이전 값까지의 합이 음수일 경우
                max = compare(max, arr[i]); //더할 필요 없이 비교해준다.
            }
            else { //이전 값까지의 합이 양수일 경우
                sum = sum + arr[i]; //다음 수들로 합이 더 커질수 있으므로 합산만 해준다.
            }
        }
    }
    printf("%d", max);
}