Bamboo Art

Zonal Computing Olympiad 2016, 15 Nov 2015
Lavanya is installing a piece of bamboo art for the Siruseri Biennale. Her installation will consist of a sequence of bamboo shoots of increasing lengths, abstractly representing the ascent of culture in the world. She also wants to arrange the bamboo shoots so that the difference in length between adjacent bamboo shoots remains the same, to maintain symmetry.She has with her a set of bamboo shoots. She will only use the bamboo shoots as they are, because cutting bamboo goes against her principles. Your task is to determine the maximum number of bamboo shoots she can use from this set as part of her installation.
Suppose she had a collection of 7 bamboo shoots of lengths 15, 8, 10, 20, 17, 13, 5. From these, she could pick bamboo shoots of lengths 13, 15 and 17 to form an installation of size 3. Alternatively, she could pick bamboo shoots of lengths 5, 10, 15 and 20 to form an installation of size 4. You can check that she cannot form an installation of size 5 or higher using this collection.
In this task, you will be given a number N, describing the number of bamboo shoots in Lavanya’s collection and the lengths of the N bamboo shoots. You may assume that no two bamboo shoots in the collection have the same length.
Your task is to output the size of the largest installation that Lavanya can create out of these bamboo shoots.
Input format
 There is only one line, which contains N + 1 space separated integers.
 The first integer is N, giving the number of bamboo shots.
 That is followed by N distinct, nonnegative integers, giving the lengths of the N bamboo shoots.
Output format
One line containing a single integer giving the size of the largest installation that Lavanya can create.
Test data
You may assume that the lengths of the bamboo shoots lie in the range 0 to 10^{5}, both inclusive. You may also assume that all bamboo shoots have distinct lengths.
Subtask 1 (40 Marks) You may assume that 1 ≤ N ≤ 400, where N is the number of bamboo shots.
Subtask 2 (60 Marks) You may assume that 1 ≤ N ≤ 2500, where N is the number of bamboo shots.
Sample Input
7 15 8 10 20 17 13 5
Sample Output
4
Explanation
N = 7, and the bamboo shoots have lengths {15, 8, 10, 20, 17, 13, 5}. This is the same example explained above. So the answer is 4.Author:  anukul 
Date Added:  22042016 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, C99 strict, CPP 4.3.2, CPP 4.9.2, CPP14, JAVA, PYTH, PYTH 3.4 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions