sntmessages's blog

sorted subsequence of length k in an unsorted array.
By sntmessages, 10 years ago, In English

Hi, I have just managed to find sorted subsequence of length 3 in an unsorted array.
I want to know how to do it to find subsequence of length k.

length of an array can be upto 100000.

Actual Question is : Given an unsorted array of n integers, find the 3 elements such that a[x] < a[y] < a[z] and x < y < z. I have done it in O(n) space and time complexity.
But I want to do it for k elements.

  • Vote: I like it
  • -6
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Do you already have a sequence that you should find or you just need k consecutive elements to be in increasing subsequence?

→ Reply
»
10 years ago, # |
  Vote: I like it +4 Vote: I do not like it

its name is longest increasing subsequence and can be O(n log n) space and time complexity

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    Hi KayacanV,
    But this will not return the elements. It will return the length only.
    Correct me if i am wrong.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Define trace[i] as the next element of the longest increasing subsequence from i->n that ends at i. Use this array to trace the elements

      → Reply