Maximum Score of Stones

In this approach, we will use recursion to solve the problem. If you are standing at any stone then you can either jump 1 or 2 steps forward or stop there and let your friend jump backward. We can recursively explore all the possible moves available to you and your friend and then finally calculate the maximum sum.

Let us define our recursive function as ‘F’, the parameters on which this function depends are (index of the stone, who is on that stone you or your friend). We can use a flag variable to determine who is on the stone. 0 means you are on the stone and 1 means your friend is on the stone. Now the recurrence relation can be given as:

If flag = 0 then

F(idx, flag) = maximum of 

‘NUMS[ idx ]’ + max( F(idx+1, 0), F(idx + 2, 0)) // i.e move forward.

and 

‘NUMS[ idx ]’ + max( F(idx-1, 1), F(idx -2, 1)) // i.e move backward.

else 

F(idx, flag) = ‘NUMS[ idx ]’ + max( F(idx-1, 1), F(idx -2, 1)) // i.e move backward

The steps are as follows:-

Function getMaxUtil( [ int ] nums, int idx, int flag):

1. If the value of the variable 'IDX' is 0 then return 'NUMS[ idx ]'.
2. If the value of 'IDX' is greater than or equal to 'N' then return -1e6.
3. If the value of 'IDX' is less than 0 then return -1e6.
4. If the value of 'FLAG' is 0:
   • Recursively call the 'getMaxUtil' function for jumps 1 and 2 forward and store the value returned by it in a variable named 'FORWARD'.
   • Recursively call the 'getMaxUtil' function for jumps 1 and 2 backward and store the value returned by it in a variable named 'BACKWARD'.
   • Return the maximum of 'FORWARD' and 'BACKWARD'.
5. Else recursively call the 'getMaxUtil' function for jumps 1 and 2 backward and return the maximum value returned by it.

Function getMaxScore([ int ] nums, int k):

1. Initialize a variable 'ANS' with value -1e8.
2. If 'K' is equal to 0, then update the value of 'ANS' to 0 and return ‘ANS’.
3. Start the game by moving forward and then going backward, recursively call the 'getMaxUtil' function for jumps 1 and 2 and store the maximum value returned by it in a variable named 'FORWARD'.
4. Also, start the game by moving backward, recursively call 'getMaxUtil' function for jump 1 and 2, and store the maximum value returned by it in a variable named 'BACKWARD'.
5. Store the maximum of forward and backward in a variable 'MAXVAL'.
6. Change the value of 'ANS' to the maximum of 'ANS' and 'MAXVAL'.
7. Return the value of the 'ANS' variable.

In this approach, the idea is to optimize the previous approach using memoization, if we observe carefully we are calculating the value of any ‘F’(idx, flag) more than once. If we can store the value of it once we have calculated it then every time this state of function will be called again then 

The steps are as follows:-

Function getMaxUtil( [ int ] nums, int idx, int flag, [ [ int ] ] dp):

1. If the value of the variable 'IDX' is 0 then return 'NUMS[ idx ]'.
2. If the value of 'IDX' is greater than or equal to 'N' then return -1e6.
3. If the value of 'IDX' is less than 0 then return -1e6.
4. If 'DP[ idx ][ flag ] != -1 then return its value.
5. If the value of 'FLAG' is 0:

• Recursively call the 'getMaxUtil' function for jumps 1 and 2 forward and store the value returned by it in a variable named 'FORWARD'.
• Recursively call the 'getMaxUtil' function for jumps 1 and 2 backward and store the value returned by it in a variable named 'BACKWARD'.
• Store the maximum of 'FORWARD' and 'BACKWARD' in 'DP[ idx ][ flag ] then return it.

1. Else recursively call the 'getMaxUtil' function for jumps 1 and 2 backward and store the maximum value returned by it in a variable named 'DP[ idx ][ flag ]' and then return it.

Function getMaxScore([ int ] nums, int k):

1. Initialize a 'DP' array of size 'N' x 2 with value -1.
2. Initialize a variable 'ANS' with value -1e8.
3. If 'K' is equal to 0, then update the value of 'ANS' to 0 and return ‘ANS’.
4. Start the game by moving forward and then going backward, recursively call the 'getMaxUtil' function for jumps 1 and 2 and store the maximum value returned by it in a variable named 'FORWARD'.
5. Also, start the game by moving backward, recursively call 'getMaxUtil' function for jump 1 and 2 and store the maximum value returned by it in a variable named 'BACKWARD'.
6. Store the maximum of forward and backward in a variable 'MAXVAL'.
7. Change the value of 'ANS' to the maximum of 'ANS' and 'MAXVAL'.
8. Return the value of the 'ANS' variable.

In this approach, we can calculate the maximum score for each stone that we can collect while jumping forward. It can be easily found by the relation. ‘DP[ i ]’ = max( DP[ i - 1 ], DP[ i - 2 ] ) + ‘NUMS[ i ]’. We can use this to find the maximum score we can collect while jumping backward. For each ‘i’th stone, the maximum score can be obtained from 3 conditions:

i. If we are jumping from ( ‘i’ + 1 )th stone to ‘i’th stone, i.e, ‘DP[ i + 1 ] + ‘NUMS [ i ].

ii. Or if we are jumping from ( ‘i’ + 2 )th stone to ‘i’th stone, i.e, DP[ i + 2 ] + ‘NUMS[ i ]’.

iii. Or, the forward was stopped on the ‘i’th stone and the friend is just starting from that stone, i.e, DP [ i ].

The maximum of these three conditions gives us the maximum score we can get for the ‘i’th stone. 

The steps are as follows:-

Function getMaxScore([ int ] nums, int k):

1. Initialize an array 'DP' of size 'N' + 1 with the value -1e9.
2. Modify the value of 'DP' at 'K' to 0.
3. Run a loop from 'i' = 'K' + 1.... 'N' - 1:

• If the value of 'i' is greater than 1:
  • Then the value of 'DP' at 'i' is the maximum value of ( 'DP[ i - 1 ], DP[ i - 2 ]') + 'NUMS[ i ]'.
  • Else the value of 'DP[ i ]' = 'DP[ i - 1 ]' + 'NUMS [ i ]'.

1. Run a loop from 'i' = 'N' - 2... 0:

• Update the value of 'DP[ i ]' to the maximum of  'DP[ i ]' and ( max( 'DP[ i + 1]', 'DP[ i + 2]' ') + 'NUMS'[ i ]).