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