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

Revision en2, by 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 ?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English X-O__O-X 2021-04-01 11:43:22 20 Tiny change: 'ere is a subsequen' -> 'ere is a strictly increasing subsequen'
en1 English X-O__O-X 2021-04-01 11:42:01 311 Initial revision (published)