Problem

Find the maximum gain in a two-players game where an array is given and each player in turn is allowed to pick one element from either end of the array. The goal of each player is to score more than his opponent. Does the player who plays first always win?

OR Given an unsorted array of pots containing coins. A and B play a game where they take turns and pick up a pot either from the beginning or the end of array. If A plays first, devise a strategy to help him win the game.

Examples

Example 1:

Input: pots = [5, 2, 7, 8]
Output: 13
A picks pot with 8 coins (array becomes [5,2,7])
B picks pot with 5 coins (array becomes [2,7])
A picks pot with 7 coins (array becomes [2])
B picks pot with 2 coins (array becomes [])

Similar Problems

Predict the Winner Problem

Solution

A greedy approach would not work since picking up 2 would leave the 100 element at one of the ends to be picked up by our opponent. A better strategy is to think in terms of subproblems

Method 1 - Recursion

Code

Java
public class Solution {
    public int maxGainRecursive(int[] nums) {
        return helper(nums, 0, nums.length - 1);
    }

    private int helper(int[] nums, int i, int j) {
        if (i > j)
            return 0;
        int sumIJ = sum(nums, i, j);
        return Math.max(nums[i] + sumIJ - nums[i] - helper(nums, i + 1, j),
            nums[j] + sumIJ - nums[j] - helper(nums, i, j - 1));
    }

    private int sum(int[] nums, int i, int j) {
        int sum = 0;
        for (int k = i; k <= j; k++) sum += nums[k];
        return sum;
    }
}
Python
def max_gain_recursive(nums):
    def helper(i, j):
        if i > j:
            return 0
        return max(
            nums[i] + sum(nums[i + 1 : j + 1]) - helper(i + 1, j),
            nums[j] + sum(nums[i:j]) - helper(i, j - 1),
        )

    return helper(0, len(nums) - 1)


# Example usage
nums = [1, 5, 3, 7, 8, 2]
print(max_gain_recursive(nums))  # Output: Maximum gain
###

Complexity

  • ⏰ Time complexity: O(2^n), because each call splits into two further calls, leading to an exponential number of calls.
  • 🧺 Space complexity: O(n)

Method 2 - Top Down DP

Code

Java
public class Solution {
    public int maxGainTopDown(int[] nums) {
        int n = nums.length;
        Integer[][] memo = new Integer[n][n];
        return helper(nums, 0, n - 1, memo);
    }

    private int helper(int[] nums, int i, int j, Integer[][] memo) {
        if (i > j)
            return 0;
        if (memo[i][j] != null)
            return memo[i][j];
        int sumIJ = sum(nums, i, j);
        memo[i][j] =
            Math.max(nums[i] + sumIJ - nums[i] - helper(nums, i + 1, j, memo),
                nums[j] + sumIJ - nums[j] - helper(nums, i, j - 1, memo));
        return memo[i][j];
    }

    private int sum(int[] nums, int i, int j) {
        int sum = 0;
        for (int k = i; k <= j; k++) sum += nums[k];
        return sum;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {1, 5, 3, 7, 8, 2};
        System.out.println(
            solution.maxGainTopDown(nums)); // Output: Maximum gain
    }
}
Python
def max_gain_top_down(nums):
    n = len(nums)
    memo = [[None] * n for _ in range(n)]

    def helper(i, j):
        if i > j:
            return 0
        if memo[i][j] is not None:
            return memo[i][j]
        sumIJ = sum(nums[i : j + 1])
        memo[i][j] = max(
            nums[i] + sumIJ - nums[i] - helper(i + 1, j),
            nums[j] + sumIJ - nums[j] - helper(i, j - 1),
        )
        return memo[i][j]

    return helper(0, len(nums) - 1)

Complexity

  • ⏰ Time complexity: O(n^2), because we fill an n x n table with results for subproblems.
  • 🧺 Space complexity: O(n^2), due to the memoization table that stores results of overlapping subproblems.

Method 3 - Bottom up DP

Code

Java
public class Solution {
    public int maxGainBottomUp(int[] nums) {
        int n = nums.length;
        int[][] dp = new int[n][n];
        int[] sumArr = new int[n + 1];

        for (int i = 0; i < n; i++) {
            sumArr[i + 1] = sumArr[i] + nums[i];
        }

        for (int length = 1; length <= n; length++) {
            for (int i = 0; i <= n - length; i++) {
                int j = i + length - 1;
                int sumIJ = sumArr[j + 1] - sumArr[i];
                if (i == j) {
                    dp[i][j] = nums[i];
                } else {
                    dp[i][j] =
                        Math.max(nums[i] + sumIJ - nums[i] - dp[i + 1][j],
                            nums[j] + sumIJ - nums[j] - dp[i][j - 1]);
                }
            }
        }

        return dp[0][n - 1];
    }
}
Python
def max_gain_bottom_up(nums):
    n = len(nums)
    dp = [[0] * n for _ in range(n)]
    sum_arr = [0] * (n + 1)

    for i in range(n):
        sum_arr[i + 1] = sum_arr[i] + nums[i]

    for length in range(1, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            sumIJ = sum_arr[j + 1] - sum_arr[i]
            if i == j:
                dp[i][j] = nums[i]
            else:
                dp[i][j] = max(
                    nums[i] + sumIJ - nums[i] - dp[i + 1][j],
                    nums[j] + sumIJ - nums[j] - dp[i][j - 1],
                )

    return dp[0][n - 1]

Complexity

  • ⏰ Time complexity: O(n^2), because we fill an n x n DP table.
  • 🧺 Space complexity: O(n^2), due to the DP table and the additional space for prefix sums.