Untitled

mail@pastecode.io avatar
unknown
c_cpp
a year ago
845 B
2
Indexable
Never
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

long long max_difference(int n, vector<long long>& powers) {
    vector<vector<long long>> dp(n, vector<long long>(n, 0));
    
    // Base cases
    for(int i = 0; i < n; i++) {
        dp[i][i] = powers[i];
    }
    
    // Filling up the DP table
    for(int length = 2; length <= n; length++) {
        for(int i = 0; i <= n - length; i++) {
            int j = i + length - 1;
            dp[i][j] = max(powers[i] - dp[i+1][j], powers[j] - dp[i][j-1]);
        }
    }
    
    return dp[0][n-1];
}

int main() {
    int n;
    cin >> n;
    
    vector<long long> powers(n);
    for(int i = 0; i < n; i++) {
        cin >> powers[i];
    }
    
    cout << abs(max_difference(n, powers)) << endl;
    
    return 0;
}