백준 - 1912 연속합

[문제 링크]

최대 연속합을 구하는 문제이다. 숫자 배열과, 최대 연속합을 저장하는 배열이 따로 더 필요하다.

구하고자 하는 숫자 배열의 가장 끝부터 차례로 내려가며, 최대연속합을 찾고자하는 배열값과, 바로 뒤 배열을 기점으로 하는 최대 연속합과의 합을 비교하여 그 최대값이 최대 연속 합이다.

밑은 예제를 돌렸을 경우의 CACHE 배열의 값이다. 맨 마지막의 CACHE값은 자기 뒤의 값이 없으므로 -1이 된다. 그 다음부터 재귀를 탈출해나가며 최대연속합을 구해나간다.

ARR	10	-4	3	1	5	6	-35	12	21	-1
CACHE	21	11	15	12	11	6	-2	33	21	-1

예를 들면 ARR이 21인 값은, 자신의 값 21과, 바로 뒤를 기점으로하는 최대 연속합과의 합인 21-1=20을 비교해서 큰 값이 그 위치를 기점으로하는 최대 연속합이다.

21인 경우에는 12와, 12+21=33 을 비교해서 큰 값이 그 위치를 기점으로하는 최대 연속합이다. 

즉 이 문제의 점화식은 다음과 같다.

DP(i) = MAX(arr[i], arr[i] + DP(i+1))

위 로직에 전체의 최대연속합을 저장하는 변수를 따로 만들어 답을 구하였다. 밑은 이를 구현한 코드이다.

#include <cstdio>
#include <algorithm>
int n,arr[100001],cache[100001];
int dp(int num){
    //기저 사례  :  마지막에 도달했을 때, 마지막 값을 시작으로 하는 최대 연속합은 자기 자신이므로. 
    if(num==n){
        cache[n] = arr[n];
        return arr[n];  
    } 
    int& ret = cache[num];
    //뒤의 값을 기준으로 하는 최대 연속값을 구하는 재귀 실행. 
    int mx = dp(num+1); 
    //점화식 : 자기 자신과, 바로 뒤의 값을 시작으로하는  최대 연속합과의 합중 최대값을 구한다. 
    ret = std::max(arr[num],arr[num]+cache[num+1]);
    //지금까지 구한 연속합중 최대값을 구한다. 
    mx = std::max(mx,ret);
    return mx;   
}
int main(){
    //초기화 
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&arr[i]);
    //구한 최대 연속합중 최대값을 찾는다. 
    printf("%d",dp(1));
}

막상 풀고 보니 재귀로 푸는 것 보다 반복문이 훨씬 깔끔하게 나올 것 같았다. 밑은 재귀를 쓰지 않고 for문으로만 구한 코드이다.

#include <cstdio>
#include <algorithm>
int n,arr[100001],cache[100001];
int dp(){
    //가장 마지막 값은 그 자체가 최대연속합이므로 배열값을 넣어준다. 
    cache[n] = arr[n]; 
    int mx = arr[n];
    for(int i = n-1;i>0;i--){
        //점화식 : 자기 자신과, 바로 뒤의 값을 시작으로하는  최대 연속값과의 합중 최대값을 구한다.
        cache[i] = std::max(arr[i],arr[i]+cache[i+1]);
        //지금까지 구한 연속합중 최대값을 구한다.
        mx = std::max(mx,cache[i]);
    } 
    return mx;
}
int main(){
    //초기화 
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&arr[i]);
    //구한 최대 연속합중 최대값을 찾는다. 
    printf("%d",dp());
}