# Appreciation

/*
 * Problem :: 2229 / 조 짜기
 *
 * Kind :: Dynamic Programming
 *
 * Insight
 * - dp[i][j] = max(i~j 번째 학생들로 조를 만들 때 조가 잘 짜여진 정도)
 *   + dp[i][j] = max({dp[i][i+1] + dp[i+2][j],
 *                     dp[i][i+2] + dp[i+3][j],
 *                     ...
 *                     })
 *
 *     # 각 구간에서의 최댓갑과 최솟값을 바로 알 수 있으면 좋을 것 같은데...
 *       그럼 미리 이를 계산해놓은 전역배열을 만들자!
 *       -> MX[i][j] = max(i~j 번째 학생들의 점수)
 *          MN[i][j] = min(i~j 번째 학생들의 점수)
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <cstring>

using namespace std;

#define endl '\n'

// Set up : Global Variables
int N;
int A[1000+1];
int dp[1000+1][1000+1];
int MN[1000+1][1000+1];
int MX[1000+1][1000+1];

// Set up : Functions Declaration
int f(int s, int e);


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    cin >> N;
    for (int i=1; i<=N; i++)
        cin >> A[i];

    // Process
    /* MX[i][j] = max(i~j 번째 학생들의 점수)
     * MN[i][j] = min(i~j 번째 학생들의 점수) */
    for (int i=1; i<=N; i++) { /* MX, MN 초기화 */
        int mx, mn;
        mx = mn = A[i];
        for (int j=i+1; j<=N; j++) {
            mx = max(mx, A[j]);
            mn = min(mn, A[j]);
            MX[i][j] = mx;
            MN[i][j] = mn;
        }
    }

    memset(dp, -1, sizeof(dp));
    int ans = f(1, N);

    // Control : Output
    cout << ans << endl;
}

// Helper Functions
int f(int s, int e)
/* max(s~e 번째 학생들로 조를 만들 때 조가 잘 짜여진 정도) 값을 반환 */
{
    if (s == e) return 0;
    if (dp[s][e] != -1) return dp[s][e];
    dp[s][e] = MX[s][e] - MN[s][e]; /* s~e 번째 학생들로 조를 만들었을 때*/
    for (int i=s; i<e; i++) {
        /* dp[s][e] = max(dp[s][e], dp[s][i]+dp[i+1][e]) */
        dp[s][e] = max(dp[s][e], f(s, i)+f(i+1, e));
    }
    return dp[s][e];
}