[1912번] 연속 합 (Dynamic Programming)

문제 출처 : 

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

알고리즘 분석 :

이 문제는, Dynamic Programming을 기반으로 풀어야 하는 문제이다.

하지만 DP를 이용해서 푼다고 할 때, 같은 알고리즘이어도 코딩이 달라 질 수 있으니 다음과 같은 사항은 주의하여야 한다.

예제 입력에서는 10 -4 3 1 5 6 -35 12 21 -1과 같이 나타나있고, -35를 더할 때 이전에 모두 더한 값이 음수가 된다.

따라서 이전까지 더해온 값 + 현재 더할 값이 음수라면 현재 더할 값을 더하면 안된다는 것을 생각하여야한다.

그리고 모든 입력이 음수로 이루어 져 있을 경우에는 그 음수 중 가장 0에 가까운 값이 큰 값임을 생각해보아야한다.

연속한 합이 최대가 되기위한 조건

1. 합이 계속해서 양수가 되어야한다.

2. 만약 연속된 수 중 음수가 있다면 이전의 합 + 현재 음수값은 양수여야한다,

3. 그렇지 않다면 음수를 만난 다음 수 부터 다시 시작한다.(더해온 값을 0으로 초기화)

예를들어

1 2 3 이면 6이 최대이고

1 -2 3이면 3이 최대이고

2 -1 3이면 4가 최대이다.

참고로 다이나믹 프로그래밍이란

어떤 조건하에 누적으로 계속 값들을 저장하며 

출력을 하기전 저장했던 값들중에서 조건에 만족하는 결과를 찾아 출력하는 방식입니다.

10 -4 3 1 5 6 -35 12 21 -1의 DP를 통해 저장된 값들은

10 6 9 10 15 21 -14 12 33 32가 저장됩니다.

소스 코드 : 

#include <stdio.h>
 
int main()
{
    int n;
    int arr[100001]; // 입력 받는 배열
    int ans[100001]; // DP에 이용되는 배열
    int max,i;
 
 
    scanf("%d", &n);
 
    for (i = 1; i <= n; i++)
        scanf("%d", &arr[i]);
 
    for (i = 1; i <= n; i++)
    {
        if (ans[i - 1] + arr[i] > arr[i]) // 이전까지 더해온 값 + 현재 더할값 > 현재 더할값 인가?
            ans[i] = ans[i - 1] + arr[i];
 
        else
            ans[i] = arr[i];
    }
 
    max = ans[1];
 
    for (i = 2; i <= n; i++)
    {
        if (ans[i] > max)
            max = ans[i];
    }
 
    printf("%d",max);
 
    return 0;
}
//                                                        This source code Copyright is Crocus 
//                                             Do you want to see more contents? click here >>