fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class LDeque {
  5. public:
  6. 	long long int difference(vector<int>& seq, int n) {
  7. 	    vector<vector<long long>> dp(n, vector<long long>(n));
  8.  
  9. 	    for(int i = 0; i < n; ++i) dp[i][i] = seq[i];
  10.  
  11. 	    for (int len = 2; len <= n; ++len) {
  12. 	        for (int l = 0;  l + len - 1 < n; ++l) {
  13. 	        	int r = l + len - 1;
  14. 	        	dp[l][r] = max(seq[l] - dp[l+1][r], seq[r] - dp[l][r-1]);
  15. 	        }
  16. 	    }
  17. 	    return dp[0][n-1];
  18. 	}
  19.  
  20. };
  21.  
  22. int main() {
  23. 	int n;
  24. 	cin >> n;
  25.  
  26. 	vector<int> seq(n);
  27.  
  28. 	for(int i = 0; i < n; ++i) cin >> seq[i];
  29.  
  30. 	LDeque obj;
  31. 	cout << obj.difference(seq, n);
  32.  
  33. 	return 0;
  34. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin 
4
10 80 90 30
stdout 
10
https://ideone.com/6IjDgE
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!