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

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) - только подумайте, как использовать свойство монотонности