[BaekJoon] 1912. 연속합

1912. 연속합

Dynamic Programming을 이용한, 아주 간단한 연속합을 구하는 문제이다.

시작 index인 0에 대하여서는 DP[0]=arr[0]값을 설정해 준 뒤, i=1부터 입력받은 정수 n까지는 for문을 탐색하며 연속합을 갱신한다.

DP[i-1]+arr[i] 값, 즉 이전 index까지의 최대 연속합에 현재 index의 value인 arr[i]값을 더한 값과, 현재 index의 value인 arr[i]값 중 더 큰 값을 DP[i]값으로 설정한다.

    DP[0]=arr[0];
    for(i=1;i<cnt;i++){
        DP[i]=maxValue(arr[i], DP[i-1]+arr[i]);
    }

DP배열의 값 중 가장 큰 값이, 가장 큰 연속합이 될 것이다.

 

전체 코드이다.

#include <stdio.h>
#include <stdlib.h>

int maxValue(int a,int b){
    return a>b ? a : b;
}
int DP[100001] = {0,};
int main(){

    int arr[100001]={0,};
    int i,cnt,n;
    int result;
    
    scanf("%d",&cnt);
    
    for(i=0;i<cnt;i++){
        scanf("%d",&n);
        arr[i]=n;
    }
    
    DP[0]=arr[0];
    for(i=1;i<cnt;i++){
        DP[i]=maxValue(arr[i], DP[i-1]+arr[i]);
    }
    
    result=-1000;
    for(i=0;i<cnt;i++)
        result=maxValue(result, DP[i]);
    
    printf("%d\n",result);
    return 0;
}