[C/C++] 백준 #1912 연속합(탐욕 알고리즘)

주어진 수열에 대해서 연속합의 최대값을 찾는 것이 이번 문제입니다.

 

Largest subarray sum problem

 

모두 다 양수라면 다 합친 것이 최대값이 될겁니다.  이와 비슷하게, 이번 알고리즘은 처음부터 차례대로 더해서 음수가 되지 않는 이상 양수 상태이면, 그것을 유지하는 것이 관건입니다.

 

알고리즘은 아주 간단합니다.

 

1. 현재의 합이 양수라면, 다음 수를 합한다.

2. 현재의 합이 음수이면, 현재의 합은 다음 수가 된다.

3. 현재의 합이 현재까지의 최대값보다 크다면, 최대값을 갱신한다.

 

제가 작성한 소스입니다.  소스는 참고용으로 봐주세요.

//--------------------------------------
//    baekjoon #1912 - Sequential Sum
//        - by Aubrey Choi
//        - created at 2019-07-03
//--------------------------------------
#include <stdio.h>

int main()
{
    int n, max, c, s, i;
    scanf("%d%d", &n,&c);
    for(i=1,max=c;i<n;i++)
    {
        scanf("%d", &s);
        c=(c < 0)?s:s+c;
        max=(c>max)?c:max;
    }
    printf("%d\n", max);
}