Jaypal and Matches.

Moderate
0/80
Average time to solve is 40m
profile
Contributed by
0 upvote
Asked in company
Amazon

Problem statement

Jaypal loves watching cricket a lot and there are ‘N’ matches scheduled for next year. He knows the amount of happiness he will get is the sum of all the matches he watched. The happiness amount for each match is denoted by the array ‘ARR’.

But the problem is that he can’t watch every match because he has to prepare for the entrance exams next year, so he decided if he watches ‘3’ matches in a row, then he will not watch the next match.

For e.g. if there are 4 matches, he can watch matches in the following possible orders:

[0, 1, 2], [0, 1, 3], [0, 2, 3], [0, 1], [0, 2], [0, 3], [0], [1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3].

So now he wants to pick such a sequence that gives him maximum happiness, as he has to prepare for his entrance exams and it would waste a lot of his time to find the best order he thought to just find the maximum happiness he can achieve by selecting any order.

He asked for your help to find the maximum happiness he can achieve. Can you help him?.

EXAMPLE : 
Input: ‘N’ = 4, ‘ARR’ = [8, 6, 6, 20]

Output: 34
In this case, the maximum possible happiness can be achieved by selecting the order: [0, 1, 3] or [0, 2, 3]. The sum of happiness for both order will be 8 + 6 + 20 = 34.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line will contain the integer ‘T’, the number of test cases.

Each test case consists of two lines.

The first line of input contains one integer, ‘N’, the number of matches scheduled.

Followed by a line containing space-separated ‘N’ positive integers, denoting the elements of the array ‘ARR’.
Output format : 
For each test case, print the maximum achievable total happiness.
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^5
0 <= ‘ARR[i]’ <= 10^4
It is guaranteed that sum of ‘N’ over all test cases is <= 10^5
Time Limit: 1 sec
Sample Input 1 :
2
5
10 8 5 7 3
8
3 1 3 3 3 5 1 3
Sample Output 1 :
28
18
Explanation Of Sample Input 1 :
For the first test case, the best order to watch matches is: [0, 1, 3, 4].

Hence, the output will be: 28

For the second test case, one of the best orders to watch matches is: [0, 1, 2, 4, 5, 7].

Hence, the output will be: 18
Sample Input 2 :
2
5
1 1 1 1 1
8
99 100 1000 865 777 696 444 1
Sample Output 2 :
4
3186
Hint

Can we try out all possible ways to watch matches and pick the order that gives maximum total happiness?

Approaches (3)
Brute Force

The idea for this approach is to try out every possible way to watch the matches and pick the order that gives us the maximum total happiness. This can be done using a recursive algorithm because the subproblem to pick order will be the same for every index of the matches.
 

So let’s suppose we are at index ‘i’, then we have four possibilities to watch matches from here onwards: 

  1. Don’t watch the ‘i’th match and move to the ‘i+1’th match.
  2. Watch the ‘i’th match and move to the ‘i+2’th match.
  3. Watch the ‘i’th and ‘i+1’th match and move to the ‘i+3’th match.
  4. Watch the ‘i’th and ‘i+1’th and ‘i+2’th match and move to the ‘i+4’th match.
     

While implementing the above algorithm we will return the maximum happiness possible for that index. And also we have to take care of the cases when the ‘i+1’th and the ‘i+2’th index doesn’t exist.
 

Algorithm:
 

// This function will return the maximum total happiness possible from the index ‘i’.

Int getMax(i, N, ARR) 

  • If ‘i>=N’
    • Return ‘0’.
  • Initialize the variable named ‘SUM’ with the value of ‘0’.
  • Initialize the variable named ‘maxHap’ with the value of ‘getMax(i+1, N, ARR)’.
  • Run a for loop from ‘i’ to ‘i+2’ with a variable named ‘j’.
    • If ‘j == N’
      • Stop the loop.
    • Add ‘ARR[j]’ to ‘SUM’.
    • Initialize the variable named ‘currHap’ with the value of ‘SUM + getMax(j+2, N, ARR)’.
    • Assign ‘maxHap’ the maximum value among ‘maxHap’ and ‘currHap’.
  • Return ‘maxHap’.
     

// The function will return the maximum total happiness possible.

Int maxHappiness(N, ARR)

  • Return ‘getMax(0, N, ARR)’.
Time Complexity

O( 4 ^ N ), Where ‘N’ is the input integer.

In the above algorithm, for every index ‘i’ we have 4 possibilities mentioned in the approach section, Hence for ‘N’ indices, we have ‘4^N’ possibilities to explore.

Hence the time complexity will be O( 4 ^ N ).

Space Complexity

O( N ), Where ‘N’ is the input integer.
 

In the above algorithm, at a certain instance, there can be utmost ‘(N - N/4)’ indices in the recursion stack.

Hence the space complexity will be O( N )

Code Solution
(100% EXP penalty)
Jaypal and Matches.
Full screen
Console