New update is available. Click here to update.

Solve problems & track your progress

Checkout your overall progress in every topic here

Become

Sensei

in DSA topics

Open the topic and solve more problems associated with it to improve your skills

Check out the skill meter for every topic

See how many problems you are left with to solve for cracking any stage. Score more than zero to get your progress counted.

Problem

Submissions

Mario And His Princess

Contributed by

Akhilesh Singh Bhadauria

Last Updated: 23 Feb, 2023

Medium

0/80

Avg time to solve 25 mins

Success Rate 65 %

0 upvotes

Problem Statement

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1 :

Sample Output 1 :

9
3

Explanation Of Sample Input 1 :

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.

Sample Input 2 :

Sample Output 2 :

2
6

Auto

Console