Math Dynamic Programming
Proficient Level

Implement the stoneGameOptimalDifference method that returns the best score difference when both players pick stones optimally.

You are given an array where each value represents stones in a pile. Two players take turns choosing either the leftmost or rightmost remaining pile.

Both players play optimally. Return the maximum final score difference the first player can achieve, calculated as first player's score minus second player's score.

Example 1
Input:
piles (int[]) = [5,3,4,5]
size (int) = 4
Return:
(int) 1
Example 2
Input:
piles (int[]) = [3,9,1,2]
size (int) = 4
Return:
(int) 7
Example 3
Input:
piles (int[]) = [1,5,2]
size (int) = 3
Return:
(int) -2

Use dynamic programming on intervals.

For an interval, store the best score difference the current player can achieve from that interval. If the current player picks the left pile, the opponent then gets the best difference from the remaining interval, so the net result is leftValue - dp[left + 1][right]. The same idea applies to picking the right pile.

The answer for the whole array is the best of these choices.

Pseudocode:

function stoneGameOptimalDifference(piles, size):
    dp = copy of piles
    for length from 2 to size:
        for left from 0 to size - length:
            right = left + length - 1
            chooseLeft = piles[left] - dp[left + 1]
            chooseRight = piles[right] - dp[left]
            dp[left] = max(chooseLeft, chooseRight)
    return dp[0]
Run your code to see the result.