Requires review and comments: My solution: find the continuous increasing sequences from the input followed by continues decreasing array. let there are k such array (continuous increase followed by continuous decrease) Now we have the trivial components. find sum for each such array.. and sum all those.
4 5 2 3 6 5 4 7 8 2 1 2 1 3 2 4 trivial components from the above input are (4 5 2) (3 6 5 4) (7 8 2 1) (2 1) (3 2) (4) 1 2 1 2 3 2 1 2 3 2 1 2 1 2 1 2 <--- and candies for them are solution. solutions for the trivial are simple.. things become interesting when teacher arranges in circle instead of line.. -------------------------------------------------------------------------------------------------------------- On Sunday, 8 July 2012 08:26:11 UTC-4, g4ur4v wrote: > Alice is a teacher of kindergarten. She wants to give some candies to > the children in her class. All the children sit in a line and each > of them has a rating score according to his or her usual > performance. Alice wants to give at least 1 candy for each children. > Because children are somehow jealousy. Alice must give her candies > according to their ratings subjects to for any adjacent 2 children if > one's rating is higher than the other he/she must get more candies > than the other. Alice wants to save money so she wants to give as few > as candies in total. > > > Input > > The first line of the input is an integre N, the number of children in > Alice's class. Each of the following N lines contains an integer > indicates the rating of each child. > > Ouput > > On the only line of the output print an integer describing the minimum > number of candies Alice must give. > > Sample Input > > 3 > 1 > 2 > 2 > > Sample Ouput > > 4 > > Explanation > > The number of candies Alice must give are 1,2 and 1. > > Constraints: > > N and the rating of each children is no larger than 10^5. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/SBGlA8Z32vAJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
