**PROBLEM LINK:** Game of Chefs

* Author:* Jeevansh Gagroo

*Tanay Morakhia*

**Tester:***Jeevansh Gagroo*

**Editorialist:****DIFFICULTY**

Hard

**PREREQUISITES**

Dynamic Programming

**EXPLANATION**

**Some Observations:**

- The trick here is to see that since the sum of the two players’ scores is the sum of the input list, Player 1 tries to maximize score1−score2, while Player 2 tries to minimize it.
- Let A
_{i}denote the value of the i_{th}number. Let dp[i][j] denote the difference between the score of the first player and the second player, score1 - score2 if they play the game between the indices i and j. - For every interval (i, j) there is a fixed person who is going to be playing on that interval. dp[i][j] stores the difference between the scores of the person who is playing on that interval and then person who plays next if they are only allowed to use that interval. Since the person playing can only take the ends of the intervals, only i and j are available.
- Call the person taking currently A. If he takes i, then the interval becomes (i + 1, j). dp[i + 1][j] stores the value of B- A, so you subtract it from a[i] to get A + a[i] - B which is the value for the current segment if A takes i. It is very similar for if A takes j, and you compare them to get dp[i][j]. dp[i][j] = max(a[i] - dp[i + 1][j], a[j] - dp[i][j - 1]).

**For better explanation refer:** Explanation

**SOLUTION**

* C++ Solution:* Game of Chefs C++ Solution

*Game of Chefs Python Solution*

**Python Solution:***Game of Chefs Java Solution*

**Java Solution:**