Last Updated: 31 Jul, 2022
Jaypal and Matches.
Moderate
Asked in company
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.
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
Approaches
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:
- Don’t watch the ‘i’th match and move to the ‘i+1’th match.
- Watch the ‘i’th match and move to the ‘i+2’th match.
- Watch the ‘i’th and ‘i+1’th match and move to the ‘i+3’th match.
- 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’.
- If ‘j == N’
- Return ‘maxHap’.
// The function will return the maximum total happiness possible.
Int maxHappiness(N, ARR)
- Return ‘getMax(0, N, ARR)’.
In the previous brute force approach, we tried out every possible order to watch matches and pick the one that gives maximum total happiness among all possible combinations. But if we observe more precisely there are many overlapping subproblems, that are recalculated again and again which in turn increases the time complexity.
For e.g. if we are index ‘X’ then we make a recursive call to find the maximum happiness for the indices ‘X+1’, ‘X+2’, ‘X+3’, and ‘X+4’.
Now at index ‘X+1’, we will make a recursive call to find the maximum happiness for the indices ‘X+2’, ‘X+3’, ‘X+4’, and ‘X+5’.
So it clearly visible that the maximum total happiness for the index ‘X+2’, ‘X+3’, and ‘X+4’ is recalculated which can be avoided if we memoize the maximum total happiness for this index in the first time of calculation.
We can create an array, let’s call it ‘DP’ of length ‘N’. Where ‘DP[i]’ denotes the maximum total happiness achievable from the index ‘i’ to ‘N-1’.
Algorithm:
// This function will return the maximum total happiness possible from the index ‘i’.
Int getMax(i, N, ARR, DP)
- If ‘i>=N’
- Return ‘0’.
- If ‘DP[i] != -1’
- Return ‘DP[i]’.
- Initialize the variable named ‘SUM’ with the value of ‘0’.
- Initialize the variable named ‘maxHap’ with the value of ‘getMax(i+1, N, ARR, DP)’.
- 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, DP)’.
- Assign ‘maxHap’ the maximum value among ‘maxHap’ and ‘currHap’.
- If ‘j == N’
- Assign ‘DP[i]’ the value of ‘maxHap’.
- Return ‘DP[i]’.
// The function will return the maximum total happiness possible.
Int maxHappiness(N, ARR)
- Create an array ‘DP’ of length ‘N’ with the initial value of ‘-1’.
- Return ‘getMax(0, N, ARR, DP)’.
In the above memoization approach, we store the maximum total happiness value possible for every index ‘0’ to ‘N-1’ in the ‘DP’ array, but if we observe more precisely for any index ‘i’ we only need the ‘DP’ value for indices ‘i+1’, ‘i+2’, ‘i+3’ and ‘i+4’ respectively.
And if we look at it in a reverse manner, we only need the values of indices ‘i-4’, ‘i-3’, ‘i-2’, and ‘i-1’ only, the ‘DP’ definition for this reverse manner will be :
‘DP[i]’, denotes the maximum possible total happiness we can get by watching the matches from ‘0’th to ‘i’th index.
And the transition will be:
DP[i] = max(DP[i-1], ARR[i] + DP[i-2], ARR[i] + ARR[i-1] + DP[i-3], ARR[i] + ARR[i-1] + ARR[i-2] + DP[i-4]).
So we can maintain a ‘DP’ array of length ‘4’ and update the ‘DP’ value accordingly before moving to the next index.
Algorithm:
// The function will return the maximum total happiness possible.
Int maxHappiness(N, ARR)
- Create an array ‘DP’ of length ‘4’ with the initial value of ‘0’.
- Run a for loop from ‘0’ to ‘N-1’ with a variable named ‘i’.
- Initialize the variable named ‘k’ with the value of ‘3’.
- Initialize the variable named ‘maxHap’ with the value of ‘DP[k]’.
- Initialize the variable named ‘SUM’ with the value of ‘0’.
- Run a for loop from ‘0’ to ‘2’ with a variable named ‘j’.
- If ‘(i-j)< 0’
- Stop the loop.
- Add ‘ARR[i-j]’ to ‘SUM’.
- Decrement ‘k’ by ‘1’.
- Initialize the variable named ‘currHap’ with the value of ‘SUM + DP[k]’.
- Assign ‘maxHap’ the maximum value among ‘maxHap’ and ‘currHap’.
- If ‘(i-j)< 0’
- Run a for loop ‘0’ to ‘2’ with a variable named ‘j’
- Assign ‘DP[j]’ the value of ‘DP[j+1]’.
- Assign ‘DP[3]’ the value of ‘maxHap’.
- Return ‘DP[3]’.