TopCoder problem "TriangularSubsequence" used in TCHS08 Round 2 (Division I Level Two)



Problem Statement

    

Three numbers x, y and z are said to satisfy the triangle inequality if x + y > z, x + z > y, and y + z > x.

The sequence of integers b[0], b[1], ..., b[n-1] is said to be triangular if b[i], b[j] and b[k] satisfy the triangle inequality for all distinct values of i, j and k.

You are given an integer sequence as a int[] a. Return the length of the longest subsequence of a that is triangular. A subsequence of a sequence is obtained by removing zero or more elements from the sequence.

 

Definition

    
Class:TriangularSubsequence
Method:longest
Parameters:int[]
Returns:int
Method signature:int longest(int[] a)
(be sure your method is public)
    
 

Constraints

-a will contain between 1 and 50 elements, inclusive.
-Each element of a will be between 1 and 10^9, inclusive.
 

Examples

0)
    
{2,3,4,1,3,4,5}
Returns: 5
The subsequence {2,3,4,3,4} is the longest triangular subsequence.
1)
    
{1,2,3}
Returns: 2
Note that a sequence of length 2 is always triangular.
2)
    
{1,1,1,1,1,1,1,1}
Returns: 8
The whole sequence is triangular.
3)
    
{1,1,1,1000000000,1000000000,1000000000}
Returns: 4
4)
    
{1000000000}
Returns: 1

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8580

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=11151&pm=8580

Writer:

andrewzta

Testers:

PabloGilberto , Olexiy , marek.cygan , ivan_metelsky

Problem categories:

Simple Math, Simple Search, Iteration