Optimal Strategy for a Game | Set 3

0 0 19 minutes read

Consider a row of n coins of values v1 . . . vn, where n is even. We play a game against an opponent by alternating turns. In each turn, a player selects either the first or last coin from the row, removes it from the row permanently, and receives the value of the coin. Determine the maximum possible amount of money we can definitely win if we move first.
Also, print the sequence of moves in the optimal game. As many sequences of moves may lead to the optimal answer, you may print any valid sequence.

Before the sequence, the part is already discussed in these articles.

Examples:

Input: 10 80 90 30
Output: 110 RRRL
Explanation:
P1 picks 30, P2 picks 90, P1 picks 80 and finally P2 picks 10.
Score obtained by P1 is 80 + 30 = 110
Max possible score for player 1 is : 110
Optimal game moves are : RRRL

Input: 10 100 10
Output: 20 RRL

Approach:
In each turn(except the last) a player will have two options either to pick the bag on the left or to pick the bag on the right of the row. Our focus is to evaluate the maximum score attainable by P1, let it be S. P1 would like to choose the maximum possible score in his turn whereas P2 would like to choose the minimum score possible for P1.
So P1 focuses on maximizing S, while P2 focuses on minimizing S.

Naive Approach:

We can write a brute force recursive solution to the problem which simulates all the possibilities of the game and finds the score that is maximum under the given constraints.
The function maxScore returns the maximum possible score for player 1 and also the moves that take place through the course of the game.
Since the function needs to return both the maximum possible score and the moves that lead to that score, we use a pair of integer and string.
The string that represents the moves of the game consists of chars ‘L’ and ‘R’ meaning that the leftmost or the rightmost bag was picked respectively.

Below is the implementation of the above approach:

C++

// C++ implementation
#include <bits/stdc++.h>
using namespace std;
 
// Calculates the maximum score
// possible for P1 If only the
// bags from beg to ed were available
pair<int, string> maxScore(vector<int> money,
                           int beg,
                           int ed)
{
    // Length of the game
    int totalTurns = money.size();
 
    // Which turn is being played
    int turnsTillNow = beg
                       + ((totalTurns - 1) - ed);
 
    // Base case i.e last turn
    if (beg == ed) {
 
        // if it is P1's turn
        if (turnsTillNow % 2 == 0)
            return { money[beg], "L" };
 
        // if P2's turn
        else
            return { 0, "L" };
    }
 
    // Player picks money from
    // the left end
    pair<int, string> scoreOne
        = maxScore(money,
                   beg + 1,
                   ed);
 
    // Player picks money from
    // the right end
    pair<int, string> scoreTwo
        = maxScore(money, beg, ed - 1);
 
    if (turnsTillNow % 2 == 0) {
 
        // if it is player 1's turn then
        // current picked score added to
        // his total. choose maximum of
        // the two scores as P1 tries to
        // maximize his score.
        if (money[beg] + scoreOne.first
            > money[ed] + scoreTwo.first) {
            return { money[beg] + scoreOne.first,
                     "L" + scoreOne.second };
        }
        else
            return { money[ed] + scoreTwo.first,
                     "R" + scoreTwo.second };
    }
 
    // if player 2's turn don't add
    // current picked bag score to
    // total. choose minimum of the
    // two scores as P2 tries to
    // minimize P1's score.
    else {
 
        if (scoreOne.first < scoreTwo.first)
            return { scoreOne.first,
                     "L" + scoreOne.second };
        else
            return { scoreTwo.first,
                     "R" + scoreTwo.second };
    }
}
 
// Driver Code
int main()
{
    // Input array
    int ar[] = { 10, 80, 90, 30 };
 
    int arraySize = sizeof(ar) / sizeof(int);
 
    vector<int> bags(ar, ar + arraySize);
 
    // Function Calling
    pair<int, string> ans
        = maxScore(bags,
                   0,
                   bags.size() - 1);
    cout << ans.first << " " << ans.second << endl;
    return 0;
}

Java

/*package whatever //do not write package name here */
import java.util.*;
 
class GFG {
 
  static class Pair<K, V> {
    K key;
    V value;
 
    public Pair(K first, V second)
    {
      this.key = first;
      this.value = second;
    }
  }
 
  // Calculates the maximum score
  // possible for P1 If only the
  // bags from beg to ed were available
  static Pair<Integer, String>
    maxScore(int []money, int beg, int ed)
  {
 
    // Length of the game
    int totalTurns = money.length;
 
    // Which turn is being played
    int turnsTillNow
      = beg + ((totalTurns - 1) - ed);
 
    // Base case i.e last turn
    if (beg == ed) {
 
      // if it is P1's turn
      if (turnsTillNow % 2 == 0)
        return new Pair<Integer, String>(
        money[beg], "L");
 
      // if P2's turn
      else
        return new Pair<Integer, String>(0, "L");
    }
 
    // Player picks money from
    // the left end
    Pair<Integer, String> scoreOne
      = maxScore(money, beg + 1, ed);
 
    // Player picks money from
    // the right end
    Pair<Integer, String> scoreTwo
      = maxScore(money, beg, ed - 1);
 
    if (turnsTillNow % 2 == 0) {
 
      // if it is player 1's turn then
      // current picked score added to
      // his total. choose maximum of
      // the two scores as P1 tries to
      // maximize his score.
      if (money[beg] + scoreOne.key
          > money[ed] + scoreTwo.key) {
        return new Pair<Integer, String>(money[beg] + scoreOne.key,"L" + scoreOne.value);
      }
      else
        return new Pair<Integer, String>(
        money[ed] + scoreTwo.key,
        "R" + scoreTwo.value);
    }
 
    // if player 2's turn don't add
    // current picked bag score to
    // total. choose minimum of the
    // two scores as P2 tries to
    // minimize P1's score.
    else {
 
      if (scoreOne.key < scoreTwo.key)
        return new Pair<Integer, String>(
        scoreOne.key, "L" + scoreOne.value);
      else
        return new Pair<Integer, String>(
        scoreTwo.key + 110,
        "R" + scoreTwo.value);
    }
 
 
  }
 
  public static void main(String[] args)
  {
    int[] ar = { 10, 80, 90, 30 };
 
    int arraySize = ar.length;
 
    int []bags = new int[arraySize];
 
    // Function Calling
    Pair<Integer, String> ans
      = maxScore(bags, 0, bags.length - 1);
    System.out.println(ans.key + " " + ans.value);
  }
}
 
// This code is contributed by aadityaburujwale.

Python3

# Python3 implementation
 
# Calculates the maximum score
# possible for P1 If only the
# bags from beg to ed were available
def maxScore( money, beg, ed):
     
    # Length of the game
    totalTurns = len(money)
     
    # Which turn is being played
    turnsTillNow = beg + ((totalTurns - 1) - ed)
     
    # Base case i.e last turn
    if (beg == ed):
         
        # if it is P1's turn
        if (turnsTillNow % 2 == 0): 
            return  [money[beg], "L"]
             
        # if P2's turn
        else:
            return [0, "L"]
             
    # Player picks money from
    # the left end
    scoreOne = maxScore(money, beg + 1, ed)
     
    # Player picks money from
    # the right end
    scoreTwo = maxScore(money, beg, ed - 1)
     
    if (turnsTillNow % 2 == 0):
         
        # If it is player 1's turn then
        # current picked score added to
        # his total. choose maximum of
        # the two scores as P1 tries to
        # maximize his score.
        if (money[beg] + scoreOne[0] > 
             money[ed] + scoreTwo[0]):
            return [money[beg] + scoreOne[0], 
                           "L" + scoreOne[1]]
        else:
            return [money[ed] + scoreTwo[0], 
                          "R" + scoreTwo[1]]
             
    # If player 2's turn don't add
    # current picked bag score to
    # total. choose minimum of the
    # two scores as P2 tries to
    # minimize P1's score.
    else:
        if (scoreOne[0] < scoreTwo[0]):
            return[scoreOne[0], "L" + scoreOne[1]]
        else:
            return[scoreTwo[0], "R" + scoreTwo[1]]
 
# Driver Code
 
# Input array
ar =  [ 10, 80, 90, 30 ]
arraySize = len(ar)
bags = ar
 
# Function Calling
ans = maxScore(bags, 0, arraySize - 1)
print(ans[0], ans[1])
 
# This code is contributed by shivani

C#

// C# implementation
using System;
using System.Collections.Generic;
class GFG {
     
    // Calculates the maximum score
    // possible for P1 If only the
    // bags from beg to ed were available
    static Tuple<int,string> maxScore(List<int> money, int beg, int ed)
    {
      
        // Length of the game
        int totalTurns = money.Count;
      
        // Which turn is being played
        int turnsTillNow = beg + ((totalTurns - 1) - ed);
      
        // Base case i.e last turn
        if (beg == ed)
        {
      
            // if it is P1's turn
            if (turnsTillNow % 2 == 0)
                return new Tuple<int,string>(money[beg], "L");
      
            // if P2's turn
            else
                return new Tuple<int,string>(0, "L");
        }
      
        // Player picks money from
        // the left end
        Tuple<int,string> scoreOne = maxScore(money, beg + 1, ed);
      
        // Player picks money from
        // the right end
        Tuple<int,string> scoreTwo = maxScore(money, beg, ed - 1);
      
        if (turnsTillNow % 2 == 0)
        {
      
            // if it is player 1's turn then
            // current picked score added to
            // his total. choose maximum of
            // the two scores as P1 tries to
            // maximize his score.
            if (money[beg] + scoreOne.Item1
                > money[ed] + scoreTwo.Item1)
            {
                return new Tuple<int,string>(money[beg] + scoreOne.Item1, "L" + scoreOne.Item2);
            }
            else
                return new Tuple<int,string>(money[ed] + scoreTwo.Item1, "R" + scoreTwo.Item2);
        }
      
        // if player 2's turn don't add
        // current picked bag score to
        // total. choose minimum of the
        // two scores as P2 tries to
        // minimize P1's score.
        else {
      
            if (scoreOne.Item1 < scoreTwo.Item1)
                return new Tuple<int,string>(scoreOne.Item1, "L" + scoreOne.Item2);
            else
                return new Tuple<int,string>(scoreTwo.Item1+110, "R" + scoreTwo.Item2);
        }
    }
 
  static void Main() {
    // Input array
    int[] ar = { 10, 80, 90, 30 };
  
    int arraySize = ar.Length;
  
    List<int> bags = new List<int>(new int[arraySize]);
  
    // Function Calling
    Tuple<int, string> ans = maxScore(bags, 0, bags.Count - 1);
    Console.Write(ans.Item1 + " " + ans.Item2);
  }
}
 
// This code is contributed by suresh07.

Javascript

<script>
// Javascript implementation
 
// Calculates the maximum score
// possible for P1 If only the
// bags from beg to ed were available
function maxScore(money, beg, ed)
{
 
    // Length of the game
    let totalTurns = money.length;
 
    // Which turn is being played
    let turnsTillNow = beg + ((totalTurns - 1) - ed);
 
    // Base case i.e last turn
    if (beg == ed)
    {
 
        // if it is P1's turn
        if (turnsTillNow % 2 == 0)
            return [money[beg], "L"];
 
        // if P2's turn
        else
            return [0, "L"];
    }
 
    // Player picks money from
    // the left end
    let scoreOne = maxScore(money, beg + 1, ed);
 
    // Player picks money from
    // the right end
    let scoreTwo = maxScore(money, beg, ed - 1);
 
    if (turnsTillNow % 2 == 0) 
    {
 
        // if it is player 1's turn then
        // current picked score added to
        // his total. choose maximum of
        // the two scores as P1 tries to
        // maximize his score.
        if (money[beg] + scoreOne[0]
            > money[ed] + scoreTwo[0]) 
        {
            return [money[beg] + scoreOne[0], "L" + scoreOne[1]];
        }
        else
            return [money[ed] + scoreTwo[[0]], "R" + scoreTwo[1]];
    }
 
    // if player 2's turn don't add
    // current picked bag score to
    // total. choose minimum of the
    // two scores as P2 tries to
    // minimize P1's score.
    else {
 
        if (scoreOne.first < scoreTwo.first)
            return [scoreOne[0], "L" + scoreOne[1]];
        else
            return [scoreTwo[0], "R" + scoreTwo[1]];
    }
}
 
// Driver Code
 
// Input array
let ar = [10, 80, 90, 30];
let arraySize = ar.length;
let bags = ar;
 
// Function Calling
let ans = maxScore(bags, 0, bags.length - 1);
document.write(ans[0] + " " + ans[1] + "<br>");
 
// This code is contributed by gfgking.
</script>

Output:

110 RRRL

The time complexity of the above approach is exponential.

Optimal Approach:
We can solve this problem by using dynamic programming in $O(n^{2})$ time and space complexity.

If we store the best possible answers for all the bags from some beginning i to some ending j then there can be at most $n^{2}$ such different subproblems.
Let dp(i, j) represent the max score P1 can attain if the only remaining bags in the row start from i and end at j. Then the following hold:
- if it is P1’s turn
  - dp(i, j) = maximum of score of bag i + dp(i+1, j) or score of bag j + dp(i, j-1).
- if it is P2’s turn
  - dp(i, j) = minimum of dp(i+1, j) or dp(i, j-1).
    Since the current bag’s score goes to P2 we don’t add it to dp(i, j).
To keep the track of the moves that take place at a given state we keep an additional boolean matrix which allows us to reconstruct the entire game moves that lead to the maximum score.
The matrix leftBag(i, j) represents a state in which only the bag from i to j are present. leftBag(i, j) is 1 if it is optimal to pick the leftBag otherwise it is 0.
The function getMoves uses this matrix to reconstruct the correct moves.

Below is the implementation of the above approach:

C++

// C++ implementation
#include <bits/stdc++.h>
#define maxSize 3000
 
using namespace std;
 
// dp(i, j) is the best
// score possible if only
// the bags from i, j were
// present.
 
int dp[maxSize][maxSize];
 
// leftBag(i, j) is 1 if in the
// optimal game the player picks
// the leftmost bag when only the
// bags from i to j are present.
 
bool leftBag[maxSize][maxSize];
 
// Function to calculate the maximum
// value
int maxScore(vector<int> money)
{
    // we will fill the dp table
    // in a bottom-up manner. fill
    // all states that represent
    // lesser number of bags before
    // filling states that represent
    // higher number of bags.
    // we start from states dp(i, i)
    // as these are the base case of
    // our DP solution.
    int n = money.size();
    int totalTurns = n;
 
    // turn = 1 if it is player 1's
    // turn else 0. Who gets to pick
    // the last bag(bottom-up so we
    // start from last turn)
    bool turn
        = (totalTurns % 2 == 0) ? 0 : 1;
 
    // if bag is picked by P1 add it
    // to the ans else 0 contribution
    // to score.
    for (int i = 0; i < n; i++) {
        dp[i][i] = turn ? money[i] : 0;
        leftBag[i][i] = 1;
    }
 
    // 2nd last bag is picked by
    // the other player.
    turn = !turn;
 
    // sz represents the size
    // or number of bags in
    // the state dp(i, i+sz)
    int sz = 1;
 
    while (sz < n) {
 
        for (int i = 0; i + sz < n; i++) {
            int scoreOne = dp[i + 1][i + sz];
            int scoreTwo = dp[i][i + sz - 1];
 
            // First player
            if (turn) {
                dp[i][i + sz]
                    = max(money[i] + scoreOne,
                          money[i + sz] + scoreTwo);
 
                // if leftBag has more profit
                if (money[i] + scoreOne
                    > money[i + sz] + scoreTwo)
                    leftBag[i][i + sz] = 1;
 
                else
                    leftBag[i][i + sz] = 0;
            }
 
            // second player
            else {
                dp[i][i + sz]
                    = min(scoreOne,
                          scoreTwo);
 
                if (scoreOne < scoreTwo)
                    leftBag[i][i + sz] = 1;
 
                else
                    leftBag[i][i + sz] = 0;
            }
        }
 
        // Give turn to the
        // other player.
        turn = !turn;
 
        // Now fill states
        // with more bags.
        sz++;
    }
 
    return dp[0][n - 1];
}
 
// Using the leftBag matrix,
// generate the actual game
// moves that lead to the score.
string getMoves(int n)
{
    string moves;
    int left = 0, right = n - 1;
 
    while (left <= right) {
 
        // if the bag is picked from left
        if (leftBag[left][right]) {
            moves.push_back('L');
            left++;
        }
 
        else {
            moves.push_back('R');
            right--;
        }
    }
    return moves;
}
 
// Driver Code
int main()
{
    int ar[] = { 10, 80, 90, 30 };
    int arraySize = sizeof(ar) / sizeof(int);
 
    vector<int> bags(ar, ar + arraySize);
    int ans = maxScore(bags);
 
    cout << ans << " " << getMoves(bags.size());
    return 0;
}

Java

// Java Implementation
public class Main
{
    static int maxSize = 3000;
       
    // dp(i, j) is the best
    // score possible if only
    // the bags from i, j were
    // present.
    static int[][] dp = new int[maxSize][maxSize];
    
    // leftBag(i, j) is 1 if in the
    // optimal game the player picks
    // the leftmost bag when only the
    // bags from i to j are present.
    static boolean[][] leftBag = new boolean[maxSize][maxSize];
   
    // Function to calculate the maximum
    // value
    static int maxScore(int[] money)
    {
       
        // we will fill the dp table
        // in a bottom-up manner. fill
        // all states that represent
        // lesser number of bags before
        // filling states that represent
        // higher number of bags.
        // we start from states dp(i, i)
        // as these are the base case of
        // our DP solution.
        int n = money.length;
        int totalTurns = n;
   
        // turn = 1 if it is player 1's
        // turn else 0. Who gets to pick
        // the last bag(bottom-up so we
        // start from last turn)
        boolean turn = (totalTurns % 2 == 0) ? false : true;
   
        // if bag is picked by P1 add it
        // to the ans else 0 contribution
        // to score.
        for (int i = 0; i < n; i++) {
            dp[i][i] = turn ? money[i] : 0;
            leftBag[i][i] = true;
        }
   
        // 2nd last bag is picked by
        // the other player.
        turn = !turn;
   
        // sz represents the size
        // or number of bags in
        // the state dp(i, i+sz)
        int sz = 1;
   
        while (sz < n) {
   
            for (int i = 0; i + sz < n; i++) {
                int scoreOne = dp[i + 1][i + sz];
                int scoreTwo = dp[i][i + sz - 1];
   
                // First player
                if (turn) {
                    dp[i][i + sz] = Math.max(money[i] + scoreOne, money[i + sz] + scoreTwo);
   
                    // if leftBag has more profit
                    if (money[i] + scoreOne > money[i + sz] + scoreTwo)
                        leftBag[i][i + sz] = true;
   
                    else
                        leftBag[i][i + sz] = false;
                }
   
                // second player
                else {
                    dp[i][i + sz] = Math.min(scoreOne, scoreTwo);
   
                    if (scoreOne < scoreTwo)
                        leftBag[i][i + sz] = true;
   
                    else
                        leftBag[i][i + sz] = false;
                }
            }
   
            // Give turn to the
            // other player.
            turn = !turn;
   
            // Now fill states
            // with more bags.
            sz++;
        }
   
        return dp[0][n - 1];
    }
   
    // Using the leftBag matrix,
    // generate the actual game
    // moves that lead to the score.
    static String getMoves(int n)
    {
        String moves = "";
        int left = 0, right = n - 1;
   
        while (left <= right) {
   
            // if the bag is picked from left
            if (leftBag[left][right]) {
                moves = moves + 'L';
                left++;
            }
   
            else {
                moves = moves + 'R';
                right--;
            }
        }
        return moves;
    }
     
    public static void main(String[] args) {
        for(int i = 0; i < maxSize; i++)
        {
            for(int j = 0; j < maxSize; j++)
            {
                dp[i][j] = 0;
                leftBag[i][j] = false;
            }
        }
        int[] ar = { 10, 80, 90, 30 };
        int arraySize = ar.length;
       
        int[] bags = ar;
        int ans = maxScore(bags);
       
        System.out.print(ans + " " + getMoves(bags.length));
    }
}
 
// This code is contributed by divyes072019.

Python3

# Python3 Implementation
maxSize = 3000
      
# dp(i, j) is the best
# score possible if only
# the bags from i, j were
# present.
dp = [[0 for i in range(maxSize)] for j in range(maxSize)]
 
# leftBag(i, j) is 1 if in the
# optimal game the player picks
# the leftmost bag when only the
# bags from i to j are present.
leftBag = [[False for i in range(maxSize)] for j in range(maxSize)]
 
# Function to calculate the maximum
# value
def maxScore(money):
    # we will fill the dp table
    # in a bottom-up manner. fill
    # all states that represent
    # lesser number of bags before
    # filling states that represent
    # higher number of bags.
    # we start from states dp(i, i)
    # as these are the base case of
    # our DP solution.
    n = len(money)
    totalTurns = n
 
    # turn = 1 if it is player 1's
    # turn else 0. Who gets to pick
    # the last bag(bottom-up so we
    # start from last turn)
    turn = 0 if (totalTurns % 2 == 0) else 1
 
    # if bag is picked by P1 add it
    # to the ans else 0 contribution
    # to score.
    for i in range(n):
        dp[i][i] = money[i] if turn else 0
        leftBag[i][i] = 1
 
    # 2nd last bag is picked by
    # the other player.
    turn = not turn
 
    # sz represents the size
    # or number of bags in
    # the state dp(i, i+sz)
    sz = 1
 
    while sz < n:
        i = 0
        while i + sz < n:
            scoreOne = dp[i + 1][i + sz]
            scoreTwo = dp[i][i + sz - 1]
 
            # First player
            if turn:
                dp[i][i + sz] = max(money[i] + scoreOne, money[i + sz] + scoreTwo)
 
                # if leftBag has more profit
                if (money[i] + scoreOne > money[i + sz] + scoreTwo):
                    leftBag[i][i + sz] = 1
                else:
                    leftBag[i][i + sz] = 0
 
            # second player
            else:
                dp[i][i + sz] = min(scoreOne, scoreTwo)
 
                if (scoreOne < scoreTwo):
                    leftBag[i][i + sz] = 1
                else:
                    leftBag[i][i + sz] = 0
            i += 1
 
        # Give turn to the
        # other player.
        turn = not turn
 
        # Now fill states
        # with more bags.
        sz += 1
 
    return dp[0][n - 1]
 
# Using the leftBag matrix,
# generate the actual game
# moves that lead to the score.
def getMoves(n):
    moves = ""
    left, right = 0, n - 1
 
    while (left <= right):
        # if the bag is picked from left
        if (leftBag[left][right]):
            moves = moves + 'L'
            left += 1
        else:
           moves = moves + 'R'
           right -= 1
    return moves
 
ar = [ 10, 80, 90, 30 ]
arraySize = len(ar)
 
bags = ar
ans = maxScore(bags)
 
print(ans, getMoves(len(bags)), sep=" ")
 
# This code is contributed by mukesh07.

C#

// C# Implementation
using System;
class GFG {
     
    static int maxSize = 3000;
      
    // dp(i, j) is the best
    // score possible if only
    // the bags from i, j were
    // present.
    static int[,] dp = new int[maxSize, maxSize];
   
    // leftBag(i, j) is 1 if in the
    // optimal game the player picks
    // the leftmost bag when only the
    // bags from i to j are present.
    static bool[,] leftBag = new bool[maxSize, maxSize];
  
    // Function to calculate the maximum
    // value
    static int maxScore(int[] money)
    {
        // we will fill the dp table
        // in a bottom-up manner. fill
        // all states that represent
        // lesser number of bags before
        // filling states that represent
        // higher number of bags.
        // we start from states dp(i, i)
        // as these are the base case of
        // our DP solution.
        int n = money.Length;
        int totalTurns = n;
  
        // turn = 1 if it is player 1's
        // turn else 0. Who gets to pick
        // the last bag(bottom-up so we
        // start from last turn)
        bool turn = (totalTurns % 2 == 0) ? false : true;
  
        // if bag is picked by P1 add it
        // to the ans else 0 contribution
        // to score.
        for (int i = 0; i < n; i++) {
            dp[i,i] = turn ? money[i] : 0;
            leftBag[i,i] = true;
        }
  
        // 2nd last bag is picked by
        // the other player.
        turn = !turn;
  
        // sz represents the size
        // or number of bags in
        // the state dp(i, i+sz)
        int sz = 1;
  
        while (sz < n) {
  
            for (int i = 0; i + sz < n; i++) {
                int scoreOne = dp[i + 1,i + sz];
                int scoreTwo = dp[i,i + sz - 1];
  
                // First player
                if (turn) {
                    dp[i,i + sz] = Math.Max(money[i] + scoreOne, money[i + sz] + scoreTwo);
  
                    // if leftBag has more profit
                    if (money[i] + scoreOne > money[i + sz] + scoreTwo)
                        leftBag[i,i + sz] = true;
  
                    else
                        leftBag[i,i + sz] = false;
                }
  
                // second player
                else {
                    dp[i,i + sz] = Math.Min(scoreOne, scoreTwo);
  
                    if (scoreOne < scoreTwo)
                        leftBag[i, i + sz] = true;
  
                    else
                        leftBag[i, i + sz] = false;
                }
            }
  
            // Give turn to the
            // other player.
            turn = !turn;
  
            // Now fill states
            // with more bags.
            sz++;
        }
  
        return dp[0,n - 1];
    }
  
    // Using the leftBag matrix,
    // generate the actual game
    // moves that lead to the score.
    static string getMoves(int n)
    {
        string moves = "";
        int left = 0, right = n - 1;
  
        while (left <= right) {
  
            // if the bag is picked from left
            if (leftBag[left,right]) {
                moves = moves + 'L';
                left++;
            }
  
            else {
                moves = moves + 'R';
                right--;
            }
        }
        return moves;
    }
     
  static void Main()
  {
    for(int i = 0; i < maxSize; i++)
    {
        for(int j = 0; j < maxSize; j++)
        {
            dp[i,j] = 0;
            leftBag[i,j] = false;
        }
    }
    int[] ar = { 10, 80, 90, 30 };
    int arraySize = ar.Length;
  
    int[] bags = ar;
    int ans = maxScore(bags);
  
    Console.Write(ans + " " + getMoves(bags.Length));
  }
}
 
// This code is contributed by decode2207.

Javascript

<script>
    // Javascript Implementation
     
    let maxSize = 3000;
     
    // dp(i, j) is the best
    // score possible if only
    // the bags from i, j were
    // present.
     
    let dp = new Array(maxSize);
    for(let i = 0; i < maxSize; i++)
    {
        dp[i] = new Array(maxSize);
        for(let j = 0; j < maxSize; j++)
        {
            dp[i][j] = 0;
        }
    }
  
    // leftBag(i, j) is 1 if in the
    // optimal game the player picks
    // the leftmost bag when only the
    // bags from i to j are present.
    let leftBag = new Array(maxSize);
    for(let i = 0; i < maxSize; i++)
    {
        leftBag[i] = new Array(maxSize);
        for(let j = 0; j < maxSize; j++)
        {
            leftBag[i][j] = false;
        }
    }
 
    // Function to calculate the maximum
    // value
    function maxScore(money)
    {
        // we will fill the dp table
        // in a bottom-up manner. fill
        // all states that represent
        // lesser number of bags before
        // filling states that represent
        // higher number of bags.
        // we start from states dp(i, i)
        // as these are the base case of
        // our DP solution.
        let n = money.length;
        let totalTurns = n;
 
        // turn = 1 if it is player 1's
        // turn else 0. Who gets to pick
        // the last bag(bottom-up so we
        // start from last turn)
        let turn = (totalTurns % 2 == 0) ? 0 : 1;
 
        // if bag is picked by P1 add it
        // to the ans else 0 contribution
        // to score.
        for (let i = 0; i < n; i++) {
            dp[i][i] = turn ? money[i] : 0;
            leftBag[i][i] = 1;
        }
 
        // 2nd last bag is picked by
        // the other player.
        turn = !turn;
 
        // sz represents the size
        // or number of bags in
        // the state dp(i, i+sz)
        let sz = 1;
 
        while (sz < n) {
 
            for (let i = 0; i + sz < n; i++) {
                let scoreOne = dp[i + 1][i + sz];
                let scoreTwo = dp[i][i + sz - 1];
 
                // First player
                if (turn) {
                    dp[i][i + sz]
                        = Math.max(money[i] + scoreOne,
                              money[i + sz] + scoreTwo);
 
                    // if leftBag has more profit
                    if (money[i] + scoreOne
                        > money[i + sz] + scoreTwo)
                        leftBag[i][i + sz] = 1;
 
                    else
                        leftBag[i][i + sz] = 0;
                }
 
                // second player
                else {
                    dp[i][i + sz]
                        = Math.min(scoreOne,
                              scoreTwo);
 
                    if (scoreOne < scoreTwo)
                        leftBag[i][i + sz] = 1;
 
                    else
                        leftBag[i][i + sz] = 0;
                }
            }
 
            // Give turn to the
            // other player.
            turn = !turn;
 
            // Now fill states
            // with more bags.
            sz++;
        }
 
        return dp[0][n - 1];
    }
 
    // Using the leftBag matrix,
    // generate the actual game
    // moves that lead to the score.
    function getMoves(n)
    {
        let moves = "";
        let left = 0, right = n - 1;
 
        while (left <= right) {
 
            // if the bag is picked from left
            if (leftBag[left][right]) {
                moves = moves + 'L';
                left++;
            }
 
            else {
                   moves = moves + 'R';
                right--;
            }
        }
        return moves;
    }
     
    let ar = [ 10, 80, 90, 30 ];
    let arraySize = ar.length;
  
    let bags = ar;
    let ans = maxScore(bags);
  
    document.write(ans + " " + getMoves(bags.length));
 
// This code is contributed by divyeshrabadiya07.
</script>

Output:

110 RRRL

Time and space complexities of this approach are $O(N^{2})$ .

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!