Untitled
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; }