TCHS 08, Раунд 2, Треугольная подпоследовательность

(TriangularSubsequence)

Три числа x, y, z удовлетворяют неравенству треугольника, если выполняются условия:

x + y > z, x + z > y, y + z > x

Последовательность b₀, b₁, …, b_n-1 называется треугольной, если удовлетворяют неравенству треугольника b_i, b_j, b_k для всех разных значений i, j, k.

В заданном массиве чисел a найти длину наибольшей треугольной подпоследовательности.

Класс: TriangularSubsequence

Метод: int longest(vector<int> a)

Ограничения: a содержит от 1 до 50 элементов, 1 £ a[i] £ 10⁹.

Вход. Массив чисел a.

Выход. Длина наибольшей треугольной подпоследовательности в массиве a.

Пример входа

a

{2,3,4,1,3,4,5}

{1,2,3}

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

Пример выхода

5

2

8

РЕШЕНИЕ

обработка последовательностей

Длина искомой подпоследовательности не меняется при перестановке чисел массива a. Отсортируем числа массива по неубыванию. Если 0 < x £ y £ z, то для удовлетворения неравенства треугольника достаточно проверить неравенство x + y > z, так как остальные два выполняются автоматически.

Рассмотрим последовательность b₀, b₁, …, b_n-1, у которой b₀ £ b₁ £ … £ b_n-1. Если n £ 2, то последовательность треугольная по определению. Рассмотрим случай, когда n ³ 3. Опишем условия, при которых последовательность b_i будет треугольной. Очевидно, что b₀ + b₁ ³ b_n-1 (любая тройка чисел b_i, b_j, b_k должна удовлетворять неравенству треугольника). В то же время для любых трех индексов 0 £ i < j < k < n имеют место неравенства: b_i + b_j ≥ b₀ + b₁ > b_n-1 ≥ b_k. Отсюда следует, что последовательность b₀ £ b₁ £ … £ b_n-1 является треугольной тогда и только тогда, когда b₀ + b₁ > b_n-1.

Сортируем исходный массив а длины n. Перебираем индексы 0 £ i £ n – 3, i + 2 £ j £ n – 1, проверяя, является ли подпоследовательность a_i, a_i+1, …, a_j треугольной. Ответ будет утвердительным, если a_i + a_i+1 > a_j. В переменной res подсчитываем длину наибольшей треугольной подпоследовательности. Если длина n массива а меньше 2, то ответ равен n. Иначе перед запуском двойного цикла значение res инициализируем 2.

ПРОГРАММА

#include <cstdio>

#include <vector>

#include <algorithm>

using namespace std;

class TriangularSubsequence

{

public:

int longest(vector<int> a)

{

int i,j,res=min(2,(int)a.size());

sort(a.begin(),a.end());

for(i=0;i<a.size()-1;i++)

for(j=i+2;j<a.size();j++)

if (a[i] + a[i+1] > a[j]) res = max(res,j - i + 1);

return res;

}

};