[C언어] 백준 1912 : 연속합

백준 1912 : 연속합

 

문제 링크

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

1912번: 연속합

 

 

문제 내용

(요약) n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. 이때 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하자.

 

 

Idea

최대 부분합을 구하기 위해 첫 번째 인덱스부터 늘려가며 비교한다. 두 개의 변수(part_sum, result)를 사용하여 최대 합을 구한다.

• part_sum : 0번째 인덱스부터 직전 인덱스까지의 합과 현재 인덱스 값을 더한 값. 단, 직전까지의 합이 0보다 작다면 0으로 초기화하고 현재 인덱스 값만을 더함.
• result : 최종 결과값. part_sum과 직전 result 값 중 큰 값.

 

 

Code

#include <stdio.h>
#include <limits.h>
#define MAX(a,b) a>b?a:b
 
int main() {
    int n, num, result = INT_MIN, part_sum = 0;
    scanf("%d", &n);
 
    //n개의 정수
    while (n--) {
        scanf("%d", &num);
        part_sum = (MAX(part_sum, 0)) + num;
        result = MAX(part_sum, result);
    }
    printf("%d\n", result);
    
    return 0;
}