Maximum Score of Stones

Moderate
0/80
Average time to solve is 45m
profile
Contributed by
0 upvote

Problem statement

You and your friend are playing a game. You are given ‘N’ stones. Each stone has a value associated with it. The value of each stone is given by a 0-indexed array ‘NUMS’ where ‘NUMS[ i ]’ denotes the value of the ‘i’th stone.

The game starts with you and your friend are standing on the ‘K’th stone. The game consists of two parts:

First part consists of you jumping forward and collecting the value of stones. From any ‘i’th stone you can jump to (‘i’ + 1)th stone or (‘i’ + 2)th stone and then collect the value of that stone. You can stop at any stone anytime. You can make 0 or more than 0 moves of this kind.

Second part consists of your friend jumping backward. The stone at which you stopped, your friend will start jumping backward from that stone and collect the value of the stones. From any ‘i’th stone your friend can jump to (‘i’ - 1)th stone or (‘i’ - 2)th stone and then collect the value of that stone. Your friend can make 0 or more than 0 moves of this kind.

The index value after the jump should be inside the boundary of 0 to ‘N’-1 inclusive.

The game ends when your friend reaches the ‘0’th stone. Find the maximum score you and your friend can collect.

Note: You don’t count the value of starting stone ‘K’ at which you are initially standing but if after some operation you again return to the ‘K’th stone then you add that value to your answer.

Example: 
Input: ‘N’ = 4,  ‘NUMS’ = {2, 1, -2, 3}, ‘K’ = 1.

Output: 6.

You are standing on the stone with index 1. You can jump from stone with index 1 to stones with index 2 or 3. Jump to stone 3 and collect the value of stone 3, total score = 3.
Now you cannot make any forward jump, your friend starts his backward turn now, he can jump to stone 1 or stone 2. Jump to stone 1 and collect the value of stone 1, total score = 4.
Jump from stone 1 to stone 0 and collect the value of stone 0, total score = 6.
Hence, the maximum score that you and your friend can collect is 6.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line will contain the integer 'T', denoting the number of test cases.

The first line of each test case contains an integer ‘N’ and ‘K’ denoting the length of the array ‘NUMS an arbitrary integer. 

The second line of each test case contains ‘N’ space-separated integers.
Output format : 
For each test case, you don’t need to print anything just return the maximum value you and your friend can collect.
Note : 
You don't need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 10
1 <= N <= 10^6 
-1000 <= NUMS[ i ] <= 1000
Sum of N Over all the Test cases <= 10^6

Time Limit: 1 sec
Sample Input 1 :
2
5 2
-1 -1 2 -1 2
3 0
-2 2 2
Sample Output 1 :
3
0
Explanation Of Sample Input 1 :
For the first case:
Jump from stone 2 to stone 4, total score = 2,
Your friend jumps from stone 4 to stone 2, total score = 4,
Your friend jumps from stone 2 to stone 1, total score = 3.
Hence, the maximum score is 3.

For the second case:
Since you are already standing on stone 0, the best option is to not make any jumps.
Hence, the maximum score is 0.
Sample Input 2 :
2
6 4
-15 100 23 -23 1 15
7 6
101 110 123 -11 -12 1 -2
Sample Output 2 :
124
324
Hint

Can you think of a way to solve this problem recursively?

Approaches (3)
Recursion

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.
Time Complexity

O( 4 ^ N ), Where ‘N’ is the length of the array ’NUMS’.

 

We are exploring all possible moves and for each stone, we have roughly 4 moves, so the recursive calls grow as 1, 4, 16… 4^N
Hence the time complexity is  O( 4 ^ N ).

Space Complexity

O( N ), Where ‘N’ is the length of the array ’NUMS’.

 

The recursive stack will contain at most ‘N’ recursive calls at once.

Hence space complexity is O( N ).

Code Solution
(100% EXP penalty)
Maximum Score of Stones
Full screen
Console