Problem of the day
Mario is going to meet his princess who is in a castle and there is a path from Mario's current location to the castle. On the path to the castle, there are dragons who do not burn instead they give DIAMOND. Mario will receive DIAMOND if and only if he didn't take any diamond from the dragon standing directly before the current dragon. In general he can not take DIAMOND from two successive dragons, if he does so then the dragons will burn him.
You are in charge of controlling Mario. There are ‘N’ dragons, you are given an array ‘DIAMOND’ of length ‘N’ where DIAMOND[i] denotes the number of DIAMOND the i-th dragon will give.
The task is to collect the maximum DIAMOND for the princess. You can not take the diamonds from two successive dragons.
All the indexing in the explanation of examples and test cases is 1-based but in the input array, 0-based indexing is used.
Example:
Input: 'N' = 5, 'DIAMOND' = [1, 2, 3, 4, 5]
Output: 9
Mario can take the following combinations of DIAMOND without getting burn:-
1, 3, 5 = 1 + 3 + 5 = 9.
1, 4 = 1 + 4 = 5
1, 5 = 1+5 = 6
2, 4 = 2+4 = 6
2, 5 = 2+5 = 7
3, 5 = 3+5 = 8
Also, he can take all the DIAMOND uniquely as well means he takes DIAMOND from the single dragon but the max DIAMOND he can get is 9.
Input Format :
The first line will contain the integer 'T', denoting the number of test cases.
For each test case, the first line will contain a single integer 'N', the size of the array 'DIAMOND'
The second line of each test case will contain ‘N’ integers representing the array elements.
Output format :
For each test case, print the maximum DIAMOND Mario can get.
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
1 <= DIAMOND[i] <= 10^5
Time Limit: 1 sec
2
5
1 2 3 4 5
5
1 1 1 1 1
9
3
For the first case:
Mario can take the following combinations of DIAMOND without getting burn:-
1, 3, 5 = 1+3+5 = 9.
1, 4 = 1+4 = 5
1, 5 = 1+5 = 6
2, 4 = 2+4 = 6
2, 5 = 2+5 = 7
3, 5 = 3+5 = 8
Also, he can take all the DIAMOND uniquely as well means he takes DIAMOND from the single dragon but the max DIAMOND he can get is 9.
For the second case:
Anyhow Mario takes the diamond he can at most 3 DIAMOND by taking DIAMOND from 1, 3, and 5.
2
2
1 2
4
1 2 3 4
2
6
Can you think of some recursive solution?
There are ‘N’ dragons on the road and for each dragon, we have two choices either we take the diamond from him or we don’t take the diamond from him. We can not take DIAMOND from two successive dragons so have to make sure of that as well.
Initially, we have 0 DIAMOND and for each ‘i’ from 0 to ‘N’-1 (0-based indexing), we can take DIAMOND from the current dragon if we haven’t taken DIAMOND from the direct previous dragon of the current dragon if there are any, and for that, we will make a flag which we will make false when we take the DIAMOND and we take diamond if the flag is true and if we don’t take the diamond than make the flag true and call for the next index and return the max of the cases where we took the DIAMOND from the current dragon and we didn’t take the diamond from the current dragons.
The Steps are as follows:-
maxDiamondRec( i:int, flag:bool, DIAMOND:[], currSum:[] ):
diamondForPrincess( diamond )
O( 2 ^ N ), Where ‘N’ is the number of dragons 'DIAMOND'.
For each dragon, we either take diamonds from him or don’t take diamonds from him so we have 2 choices for each dragon and there are ‘N’ dragons. This will give TLE.
Hence Time complexity is O( 2^N ).
O( 1 ).
We are not using any extra space.
Hence space complexity is O( 1 ).