2229 조짜기

#include <stdio.h>
#include <math.h>
 
int arr[1005] = { 0 };
int dp[1005][1005] = { 0 };
 
int main() {
    int n;
    scanf("%d", &n);
 
    for (int i = 1; i <= n; i++) {
        scanf("%d", &arr[i]);
    }
 
    for (int i = 1; i <=  n; i++) {
        for (int k = 1; i + k <= n; k++) {
            dp[i][i + k] = abs(arr[i] - arr[i + k]);
        }
    }
 
    for (int d = 2; d < n; d++) {
        for (int i = 1; i + d <= n; i++) {
            int maxV = 0;
            for (int mid = i; mid + 1 <= i + d; mid++) {
                int val = dp[i][mid] + dp[mid + 1][i+d];
 
                if (maxV < val)
                    maxV = val;
            }
 
            if(dp[i][i+d]<maxV)
                dp[i][i + d] = maxV;
;        }
    }
    printf("%d", dp[1][n]);
}