Problem Statement: 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 performs the following operation K times.
The 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 the user can definitely win if the user moves first.
Note: The opponent is as clever as the user.
Examples:Â
Â
Input : array = {10, 15, 20, 9, 2, 5}, k=2Â
Output :32Â
Explanation:Â
Lets say, user has initially picked 10 and 15.Â
The value of coins which the user has is 25 andÂ
{20, 9, 2, 5} are remaining in the array.Â
In the second round, the opponent picks 20 and 9 making his value 29.Â
In the third round, the user picks 2 and 5 which makes his total value as 32.Â
Input: array = {10, 15, 20, 9, 2}, k=1Â
Output: 32Â
Â
Â
Approach:Â
A recursive solution needs to be formed and the values of sub problems needs to be stored to compute the result.Â
Taking an example to arrive at the recursive solution;
arr = {10, 15, 20, 9, 2, 5}, k=2Â
So if the user selects 10, 15 in the first turn then 20, 9, 2, 5 are left in the array.Â
But if the user selects 10, 5; then 15, 20, 9, 2 are left in the array.Â
Lastly, if the user selects 5, 2; then 10, 15, 20, 9 are left in the array.
So at any iteration after selecting k elements, a continuous subarray of length n-k is remaining for next computation.
So recursive solution can be formed where :Â
Â
S(l, r) = (sum(l, r) – sum(l+i, l+i+n-k-1))+(sum(l+i, l+i+n-k-1) – S(l+i, l+i+n-k-1))Â
where l+i+n-k-1<=rÂ
Â
Sum of chosen elements Sc=(sum(l, r) – sum(l+i, l+i+n-k-1))Â
Now the opponent will perform the next turn soÂ
Sum of Elements chosen in next steps = Total sum of present array from l to r –Â
Sum of elements chosen by opponent in next steps which is equal toÂ
Â
Nc=(sum(l+i, l+i+n-k-1) - S(l+i, l+i+n-k-1)). S(l, r) = Sc + Nc where, Nc=(sum(l+i, l+i+n-k-1) - S(l+i, l+i+n-k-1)) Sc=(sum(l, r) - sum(l+i, l+i+n-k-1))
Â
Below is the implementation of the above approach:Â
Â
C++
// C++ implementation of the above approach#include <bits/stdc++.h>using namespace std;#define ll long long intÂ
// Function to return sum of subarray from l to rll sum(int arr[], int l, int r){    // calculate sum by a loop from l to r    ll s = 0;    for (int i = l; i <= r; i++) {        s += arr[i];    }    return s;}Â
// dp to store the values of sub problemsll dp[101][101][101] = { 0 };Â
ll solve(int arr[], int l, int r, int k){    // if length of the array is less than k    // return the sum    if (r - l + 1 <= k)        return sum(arr, l, r);Â
    // if the value is previously calculated    if (dp[l][r][k])        return dp[l][r][k];Â
    // else calculate the value    ll sum_ = sum(arr, l, r);    ll len_r = (r - l + 1) - k;    ll len = (r - l + 1);    ll ans = 0;Â
    // select all the sub array of length len_r    for (int i = 0; i < len - len_r + 1; i++) {        // get the sum of that sub array        ll sum_sub = sum(arr, i + l, i + l + len_r - 1);Â
        // check if it is the maximum or not        ans = max(ans, (sum_ - sum_sub) + (sum_sub -                   solve(arr, i + l, i + l + len_r - 1, k)));    }Â
    // store it in the table    dp[l][r][k] = ans;Â
    return ans;}Â
// Driver codeint main(){Â Â Â Â int arr[] = { 10, 15, 20, 9, 2, 5 }, k = 2;Â Â Â Â int n = sizeof(arr) / sizeof(int);Â Â Â Â memset(dp, 0, sizeof(dp));Â
    cout << solve(arr, 0, n - 1, k);Â
    return 0;} |
Java
// Java implementation of the above approach class GFG{         // Function to return sum of subarray from l to r     static int sum(int arr[], int l, int r)     {         // calculate sum by a loop from l to r         int s = 0;         for (int i = l; i <= r; i++)        {             s += arr[i];         }         return s;     }          // dp to store the values of sub problems     static int dp[][][] = new int[101][101][101] ;          static int solve(int arr[], int l, int r, int k)     {         // if length of the array is less than k         // return the sum         if (r - l + 1 <= k)             return sum(arr, l, r);              // if the value is previously calculated         if (dp[l][r][k] != 0)             return dp[l][r][k];              // else calculate the value         int sum_ = sum(arr, l, r);         int len_r = (r - l + 1) - k;         int len = (r - l + 1);         int ans = 0;              // select all the sub array of length len_r         for (int i = 0; i < len - len_r + 1; i++)         {             // get the sum of that sub array             int sum_sub = sum(arr, i + l, i + l + len_r - 1);                  // check if it is the maximum or not             ans = Math.max(ans, (sum_ - sum_sub) + (sum_sub -                     solve(arr, i + l, i + l + len_r - 1, k)));         }              // store it in the table         dp[l][r][k] = ans;              return ans;     }          // Driver code     public static void main (String[] args)     {             int arr[] = { 10, 15, 20, 9, 2, 5 }, k = 2;         int n = arr.length; Â
        System.out.println(solve(arr, 0, n - 1, k));          }}Â
// This code is contributed by AnkitRai01 |
Python3
# Python3 implementation of the above approach import numpy as npÂ
# Function to return sum of subarray from l to r def Sum(arr, l, r) : Â
    # calculate sum by a loop from l to r     s = 0;     for i in range(l, r + 1) :        s += arr[i]; Â
    return s; Â
# dp to store the values of sub problems dp = np.zeros((101, 101, 101)); Â
def solve(arr, l, r, k) :Â
    # if length of the array is less than k     # return the sum     if (r - l + 1 <= k) :        return Sum(arr, l, r); Â
    # if the value is previously calculated     if (dp[l][r][k]) :        return dp[l][r][k]; Â
    # else calculate the value     sum_ = Sum(arr, l, r);     len_r = (r - l + 1) - k;     length = (r - l + 1);     ans = 0; Â
    # select all the sub array of length len_r     for i in range(length - len_r + 1) :                 # get the sum of that sub array         sum_sub = Sum(arr, i + l, i + l + len_r - 1); Â
        # check if it is the maximum or not         ans = max(ans, (sum_ - sum_sub) + (sum_sub -                            solve(arr, i + l, i + l + len_r - 1, k))); Â
    # store it in the table     dp[l][r][k] = ans; Â
    return ans; Â
Â
# Driver code if __name__ == "__main__" : Â
    arr = [ 10, 15, 20, 9, 2, 5 ]; k = 2;          n = len(arr); Â
    print(solve(arr, 0, n - 1, k)); Â
# This code is contributed by AnkitRai01 |
C#
// C# implementation of the above approach using System;Â
class GFG{         // Function to return sum of subarray from l to r     static int sum(int []arr, int l, int r)     {         // calculate sum by a loop from l to r         int s = 0;         for (int i = l; i <= r; i++)        {             s += arr[i];         }         return s;     }          // dp to store the values of sub problems     static int [,,]dp = new int[101, 101, 101] ;          static int solve(int []arr, int l, int r, int k)     {         // if length of the array is less than k         // return the sum         if (r - l + 1 <= k)             return sum(arr, l, r);              // if the value is previously calculated         if (dp[l, r, k] != 0)             return dp[l, r, k];              // else calculate the value         int sum_ = sum(arr, l, r);         int len_r = (r - l + 1) - k;         int len = (r - l + 1);         int ans = 0;              // select all the sub array of length len_r         for (int i = 0; i < len - len_r + 1; i++)         {             // get the sum of that sub array             int sum_sub = sum(arr, i + l, i + l + len_r - 1);                  // check if it is the maximum or not             ans = Math.Max(ans, (sum_ - sum_sub) + (sum_sub -                     solve(arr, i + l, i + l + len_r - 1, k)));         }              // store it in the table         dp[l, r, k] = ans;              return ans;     }          // Driver code     public static void Main ()     {        int []arr = { 10, 15, 20, 9, 2, 5 };        int k = 2;         int n = arr.Length; Â
        Console.WriteLine(solve(arr, 0, n - 1, k));     }}Â
// This code is contributed by AnkitRai01 |
Javascript
<script>Â
    // JavaScript implementation of the above approach         // Function to return sum of subarray from l to r     function sum(arr, l, r)     {         // calculate sum by a loop from l to r         let s = 0;         for (let i = l; i <= r; i++)        {             s += arr[i];         }         return s;     }            // dp to store the values of sub problems     let dp = new Array(101);     for (let i = 0; i < 101; i++)    {        dp[i] = new Array(101);        for (let j = 0; j < 101; j++)        {            dp[i][j] = new Array(101);            for (let k = 0; k < 101; k++)            {                dp[i][j][k] = 0;            }        }    }           function solve(arr, l, r, k)     {         // if length of the array is less than k         // return the sum         if (r - l + 1 <= k)             return sum(arr, l, r);                // if the value is previously calculated         if (dp[l][r][k] != 0)             return dp[l][r][k];                // else calculate the value         let sum_ = sum(arr, l, r);         let len_r = (r - l + 1) - k;         let len = (r - l + 1);         let ans = 0;                // select all the sub array of length len_r         for (let i = 0; i < len - len_r + 1; i++)         {             // get the sum of that sub array             let sum_sub = sum(arr, i + l, i + l + len_r - 1);                    // check if it is the maximum or not             ans = Math.max(ans, (sum_ - sum_sub) + (sum_sub -                     solve(arr, i + l, i + l + len_r - 1, k)));         }                // store it in the table         dp[l][r][k] = ans;                return ans;     }          let arr = [ 10, 15, 20, 9, 2, 5 ], k = 2;     let n = arr.length; Â
    document.write(solve(arr, 0, n - 1, k));      </script> |
Output:Â
32
Â
Time Complexity: O(r2)
Auxiliary Space: O(101 * 101 * 101)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
… [Trackback]
[…] Read More on to that Topic: geeksforgeeks.org/optimal-strategy-for-a-game-with-modifications/ […]
… [Trackback]
[…] Find More on to that Topic: geeksforgeeks.org/optimal-strategy-for-a-game-with-modifications/ […]