fork download
copy 
  1. #include <iostream>
  2. #include<bits/stdc++.h>
  3. #include<string>
  4. using namespace std;
  5. vector<vector<int>>DP[2];
  6. vector<int>v;
  7. int solve(int s,int e,bool me){
  8. 	if(s>e) return 0;
  9. 	if(DP[me][s][e]!=-1) return DP[me][s][e];
  10. 	if(me) return DP[me][s][e]=max(solve(s+1,e,false)+v[s],solve(s,e-1,false)+v[e]);
  11. 	return DP[me][s][e]=min(solve(s+1,e,true)-v[s],solve(s,e-1,true)-v[e]);
  12. }
  13. int getMaxScore(vector<int>nums){
  14.     v=nums;
  15. 	DP[0]=DP[1]=vector<vector<int>>(nums.size()+1,vector<int>(nums.size()+1,-1));
  16. 	int sum=0;
  17. 	for(int i=0;i<nums.size();i++) sum+=v[i];
  18.     int deff=solve(0,nums.size()-1,true);
  19.     return (sum+deff)/2;
  20. }
  21. int main(){
  22.     vector<int>v({7, 6, -5, 4, 11, 1});
  23.     cout<<getMaxScore(v)<<endl;
  24.     return 0;
  25. }
  26.  
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
13
https://ideone.com/8XDygB
language:
C++14 (gcc 8.3)
created:
4 years 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!