108: Increasing triplet subsequence

Дан массив чисел, проверьте существует ли подпоследовательность длиной три такая что array[i] < array[j] < array[k] и i < j < k

Замечание: Постарайтесь написать алгоритм который работает за время O(n)

 

Пример 1

Input:   [1, 0, 3, 5]

Output:  true

Пояснение: [1, 3, 5] или [0, 3, 5]

Пример 2

Input:   [5, 6, 4, 3]

Output:  false