CRANBROM - Editorial

Level: Medium

Concepts: Greedy,Dynamic programming, hashing

Problem link: http://www.codechef.com/CRNM2014/problems/CRANBROM

This one can be done in many ways.
Here is an O(n) solution .

Below I will outline a way where we dynamically store whatever best so far we could have earned every time we find a broom.

Whenever we have a customer we will compare the current profit with the one will be making if we sell the broom being demanded.

Pseudocode:


//initialise an array l with -1
ans=0

for  every day iterate:
    string,i=input();//take the input
    if string=='found':
        l[i]=ans
    else if l[i]>=0:
        ans=max(ans,l[i]+i)
        l[i]=-1
print ans