TriangularSubsequence | Topcoder Archive

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

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

{1,1,1,1000000000,1000000000,1000000000}

Returns: 4

```
{1000000000}
```
```
Returns: 1
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.