Alice and Bob take turns playing a game, with Alice starting first.
n stones arranged in a row. On each player’s turn, they can remove either the leftmost stone or the rightmost stone from the row and receive points equal to the sum of the remaining stones’ values in the row. The winner is the one with the higher score when there are no stones left to remove.
Bob found that he will always lose this game (poor Bob, he always loses), so he decided to minimize the score’s difference. Alice’s goal is to maximize the difference in the score.
Given an array of integers
stones[i] represents the value of the
ith stone from the left, return the difference in Alice and Bob’s score if they both play optimally.
You are given a 0-indexed integer array
nums and an integer
You are initially standing at index
0. In one move, you can jump at most
k steps forward without going outside the boundaries of the array. That is, you can jump from index
i to any index in the range
[i + 1, min(n - 1, i + k)] inclusive.
You want to reach the last index of the array (index
n - 1). Your score is the sum of all
nums[j] for each index
j you visited in the array.
Return the maximum score you can get.