구간 차의 합 최대 - 더블릿

#include <stdio.h>
#include <algorithm>
 
using namespace std;
 
int arr[200] = { 0 };       // 입력받을 배열
int dp[200][200] = { 0 };   // dp
int num[200][200] = { 0 };  // 누적 구간 수
int cut[200][200]= { 0 };   // 누적 구간 분할 위치 ex) 2 2 3 3
int result[100] = { 0 },idx=1;  // 누적 구간 인덱스 모음
 
void sumRange(int a, int b) {    // 재귀함수 이용 -> 분할 위치 추적
    if (a < cut[a][b] && cut[a][b]< b) {                
        sumRange(a, cut[a][b]);        //inorder방식의 순환
        result[idx++] = cut[a][b];  // 분할 위치를 배열에 인덱스 형태로 저장
        sumRange(cut[a][b] + 1, b);
    }    
}
 
int main() {
    int n;    // 배열의 길이
    scanf("%d", &n);
    getchar();
 
    for (int i = 1; i <= n; i++) {  //배열 입력 받기
        scanf("%d", &arr[i]);
    }
 
    //우측 하향 대각선의 방향으로 채워지므로 len 변수를 사용함
    for (int len = 1; len < n; len++) {
        for (int i = 1; i < n; i++) {
            // max, min의 값을 구함 (값의 차를 구해서 분할 여부를 판단)
            int maxNum = 0, minNum = 1000;
            if (i + len <= n) {
                for (int j = i; j <= i + len; j++) {
                    if (maxNum < arr[j]) {
                        maxNum = arr[j];
                    }
                    if (minNum > arr[j]) {
                        minNum = arr[j];
                    }
                }
                int diff = maxNum - minNum;
 
                //tmp를 통해서 각각의 분할 구간 중 최고 차이를 구함
                int tmp = 0;
                for (int j = i + 1; j <= i + len - 1; j++) {
                    if (tmp < dp[i][j] + dp[j + 1][i + len]) {
                        //분할을 했을 경우, 각각의 분할 수를 누적함
                        num[i][i + len] = num[i][j] + num[j + 1][i + len];
                        //최고의 분할 구간을 대입
                        tmp = dp[i][j] + dp[j + 1][i + len];
                        //분할을 한 위치를 저장
                        cut[i][i + len] = j;
                    }                        
                }
 
                //분할 한 것보다 그대로 그 구간에서의 최대, 최소 차이를 구한게
                //더 클 떈 num 누적 배열을 1로 바꾸고, 분할 위치도 맨 끝으로 바꾼다
                if (diff > tmp) {
                    num[i][i + len] = 1;
                    cut[i][i + len] = i + len;
                }
                // 누적 구간 차의 합을 dp에 저장함
                dp[i][i + len] = max(diff, tmp);                
            }
        }
    }
 
    printf("%d\n%d\n", dp[1][n], num[1][n]);
    sumRange(1,n);
 
    //result에 저장된건 index들이므로, 구간 길이를 구하려면 각각의 인덱스의 차를 이용
    printf("%d ", result[1]);
    for (int i = 2; i < idx; i++) {
        printf("%d ", result[i] - result[i - 1]);
    }
    printf("%d ", n - result[idx-1]);
}