1690. Stone Game VII LeetCode Solution

In this guide, you will get 1690. Stone Game VII LeetCode Solution with the best time and space complexity. The solution to Stone Game VII problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Stone Game VII solution in C++
Stone Game VII solution in Java
Stone Game VII solution in Python
Additional Resources

1690. Stone Game VII LeetCode Solution image

Problem Statement of Stone Game VII

Alice and Bob take turns playing a game, with Alice starting first.
There are 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 where 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.

Example 1:

Input: stones = [5,3,1,4,2]
Output: 6
Explanation:
– Alice removes 2 and gets 5 + 3 + 1 + 4 = 13 points. Alice = 13, Bob = 0, stones = [5,3,1,4].
– Bob removes 5 and gets 3 + 1 + 4 = 8 points. Alice = 13, Bob = 8, stones = [3,1,4].
– Alice removes 3 and gets 1 + 4 = 5 points. Alice = 18, Bob = 8, stones = [1,4].
– Bob removes 1 and gets 4 points. Alice = 18, Bob = 12, stones = [4].
– Alice removes 4 and gets 0 points. Alice = 18, Bob = 12, stones = [].
The score difference is 18 – 12 = 6.

Example 2:

Input: stones = [7,90,5,1,100,10,10,2]
Output: 122

Constraints:

n == stones.length
2 <= n <= 1000
1 <= stones[i] <= 1000

Complexity Analysis

Time Complexity: O(n^2)
Space Complexity: O(n^2)

1690. Stone Game VII LeetCode Solution in C++

class Solution {
 public:
  int stoneGameVII(vector<int>& stones) {
    const int n = stones.size();
    vector<vector<int>> mem(n, vector<int>(n));
    vector<int> prefix(n + 1);
    partial_sum(stones.begin(), stones.end(), prefix.begin() + 1);
    return stoneGameVII(stones, 0, n - 1, prefix, mem);
  }

 private:
  // Returns the maximum score you can get more than your opponent in
  // stones[i..j].
  int stoneGameVII(const vector<int>& stones, int i, int j,
                   const vector<int>& prefix, vector<vector<int>>& mem) {
    if (i == j)
      return 0;
    if (mem[i][j] > 0)
      return mem[i][j];
    // Remove stones[i] to get sum(stones[i + 1..j]).
    const int removeLeft = prefix[j + 1] - prefix[i + 1] -
                           stoneGameVII(stones, i + 1, j, prefix, mem);
    // Remove stones[j] to get sum(stones[i..j - 1]).
    const int removeRight = prefix[j] - prefix[i] -  //
                            stoneGameVII(stones, i, j - 1, prefix, mem);
    return mem[i][j] = max(removeLeft, removeRight);
  }
};
/* code provided by PROGIEZ */

1690. Stone Game VII LeetCode Solution in Java

class Solution {
  public int stoneGameVII(int[] stones) {
    final int n = stones.length;
    Integer[][] mem = new Integer[n][n];
    int[] prefix = new int[n + 1];
    for (int i = 0; i < n; ++i)
      prefix[i + 1] = prefix[i] + stones[i];
    return stoneGameVII(stones, 0, n - 1, prefix, mem);
  }

  // Returns the maximum score you can get more than your opponent in
  // stones[i..j].
  private int stoneGameVII(int[] stones, int i, int j, int[] prefix, Integer[][] mem) {
    if (i == j)
      return 0;
    if (mem[i][j] != null)
      return mem[i][j];
    // Remove stones[i] to get sum(stones[i + 1..j]).
    final int removeLeft = prefix[j + 1] - prefix[i + 1] - //
                           stoneGameVII(stones, i + 1, j, prefix, mem);

    // Remove stones[j] to get sum(stones[i..j - 1]).
    final int removeRight = prefix[j] - prefix[i] - //
                            stoneGameVII(stones, i, j - 1, prefix, mem);
    return mem[i][j] = Math.max(removeLeft, removeRight);
  }
}
// code provided by PROGIEZ

1690. Stone Game VII LeetCode Solution in Python

class Solution {
 public:
  int stoneGameVII(vector<int>& stones) {
    const int n = stones.size();
    // dp[i][j] := the maximum score you can get more than your opponent in
    // stones[i..j]
    vector<vector<int>> dp(n, vector<int>(n));
    vector<int> prefix(n + 1);

    partial_sum(stones.begin(), stones.end(), prefix.begin() + 1);

    for (int d = 1; d < n; ++d)
      for (int i = 0; i + d < n; ++i) {
        const int j = i + d;
        dp[i][j] = max(prefix[j + 1] - prefix[i + 1] - dp[i + 1][j],
                       prefix[j] - prefix[i] - dp[i][j - 1]);
      }

    return dp[0][n - 1];
  }
};
 # code by PROGIEZ