S_Neal's blog

Lexographically LIS of a fixed length.
By S_Neal, history, 6 months ago, In English

How to find the lexographically smallest Longest Increasing Subsequence of a fixed length k.where size of the array is 100000 and 1<=k<=100000.

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
6 months ago, # |
  Vote: I like it +3 Vote: I do not like it

What does " Longest Increasing Subsequence of a fixed length $$$k$$$" mean?

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

    I think he means LIS of a bunch of strings, each string of length k

    → Reply
    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      What it sounds like to me is that he wants the lexicographically smallest increasing subsequence of length $$$k$$$ in the array (i.e. Take all the increasing subsequences of length $$$k$$$. Of them choose the lexicographically smallest), but I'm not sure, so I asked

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

        Sorry for my bad English. you are right . I want the " lexicographically smallest increasing subsequence of length k in the array (i.e. Take all the increasing subsequences of length k. Of them choose the lexicographically smallest)"

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

          You can modify the $$$O(N \cdot \log N)$$$ algorithm, run it from right to left and obtain for each $$$i$$$ the smallest value for which there exists an increasing sequence of length $$$i$$$, starting with that value. Consequently you can also obtain the length of the longest increasing sequence that starts at a given index.

          Now for the construction, you want to take the smallest value that allows you to make an IS with that starting value. That is the minimum between the numbers where the max length is at least $$$k$$$. Next you want to remove all the values to the left of what you just picked up. You also want to add all the elements to the right of the first element, that have a max_length at least $$$k - 1$$$. Next you remove elements to the left, add new ones from the right, ...

          I would suggest you try on a couple small examples, $$$[5, 6, 3, 4, 1, 2]$$$, $$$[1, 2, 3]$$$, $$$[4, 7, 2, 5, 3, 1, 6, 8]$$$.

          If you don't understand something then just reply to this comment and I will do my best to explain

          → Reply