Количество треугольников из отсортированной последовательности

Question

Учитывая строго возрастающую последовательность n натуральные числа A(1) < A(2) < ... < A(n), Нам нужно найти количество треугольников с длинами сторон как 3 отдельные элементы этой последовательности.

поскольку n <= 6000проверка каждой возможной комбинации не достаточно быстра. Есть ли лучший алгоритм? Спасибо за любую помощь.

Мой псевдокод:

for i from 0 till n - 2
    for j from i+1 till n-1
        for k from j+1 till n
            if A[i] + A[j] > A[k] then count += 1
            else break

Answer 1

1. Вы можете исключить третий цикл и найти максимальное значение k с помощью двоичного поиска. Сложность O(N^2*Log(N)
2. Вы можете достичь лучшего времени - O(N^2) - просто подумайте, как использовать свойство монотонности.