PROBLEM LINK:
Practice
Contest
DIFFICULTY:
EASY
EXPLANATION:
This is a straight forward question. Link only defeats monsters which have a level greater than or equal to his.
Initially Link’s level is zero and total XP is zero. Move from left to right in the array.
If the level of the monster is greater than or equal to Link’s level, then defeat it, add the monster’s level to the total XP, and set Link’s level to the level of the monster.
Else, skip that monster.
This solution has a complexity of O(n).
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
1 Like
Wait…am i missing something?
Shouldnt it require dp? According to your given steps-
If the level of the monster is greater than or equal to Link's level, then defeat it, add the monster's level to the total XP, and set Link's level to the level of the monster.
How will you deal if monsters are like-
9 1 2 3 4 5 6 7 8
Or modifying your sample example-
2 1 2 3 2 to 4 1 2 3 2
We have to return the maximum exp he can earn, isnt it? Can someone shed some light on this?
Order of the monsters can’t be changed buddy. THats why it does not require DP
SO for your example the answer will be 9 for the first one.
I meant, we can either kill a monster or leave it. So why not leave 9 and kill “1 2 3…9” ?
I agree that the problem statement is quiete ambiguous, it does not say anything about this thing.
Your argument is perfect.
1 Like