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) =
4Returns (int)
1Example 2
Input
piles (int[]) =
[3,9,1,2]size (int) =
4Returns (int)
7Example 3
Input
piles (int[]) =
[1,5,2]size (int) =
3Returns (int)
-2Use 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]Ready to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run