Is there an increasing subsequence of length X in a given sequence of length N ? can you find it in O(n)?

Правка en2, от X-O__O-X, 2021-04-01 11:43:22

Input: a sequence <A_1, A_2, ..., A_n> of integers and an integer X.

Output: true if there is a strictly increasing subsequence of length X in sequence A, false otherwise.

Is there an O(n) algorithm for this problem ?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский X-O__O-X 2021-04-01 11:43:22 20 Tiny change: 'ere is a subsequen' -> 'ere is a strictly increasing subsequen'
en1 Английский X-O__O-X 2021-04-01 11:42:01 311 Initial revision (published)