Zonal Computing Olympiad 2009, 20 Dec 2008
10:00 am-1:00 pm IST
Problem 2 : Choosing chocolates
Santa Claus has lined up a row of bowls, each containing some chocolates. Nikhil has been told that he can pick up as many of these bowls as he wants, provided that he never picks two consecutive bowls.
Your aim is to help Nikhil choose a set of bowls so that he maximizes the number of chocolates that he picks up.
Input format
The first line of the input contains one integer N, the number of bowls. This is followed by a line containing N integers, describing the number of chocolates in each of the N bowls.
Notes
In all cases, N ≤ 100,000.
Output format
Your output should be a single line consisting of one integer, the maximum number of chocolates that Nikhil can collect.
Sample Input
10 30 10 8 20 11 12 25 13 20 19
Sample Output
95
Copyright (c) IARCS 2003-2024; Last Updated: 01 Dec 2009