Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

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.
```

Detailed explanation

```
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
```