X-O__O-X's blog

Is there an increasing subsequence of length X in a given sequence of length N ? can you find it in O(n)?
By X-O__O-X, history, 3 years ago, In English

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 ?

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

Comments Comments (13)
| Write comment?
»
3 years ago, # |
  Vote: I like it -26 Vote: I do not like it

Calculate all $$$a_{i+1}-a_i\ (1\leq i\leq n-1)$$$ and find out if there are $$$x-1$$$ or more continuous positive numbers.

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

    subsequence not subarray.

    counterexample:

    a = [1, 2, 1, 3, 1, 4, 1, 5], x = 5

    ans = true, but your condition is false.

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

I only have an $$$O(n\cdot log_2(n))$$$ solution using segment tree with coordinate compression + DP. I don't think there is a $$$O(n)$$$ solution. Not sure.

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

    Calculating LIS in O(nlog(n)) is not an option here ?

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

      You can just get the LIS of the sequence. If it is bigger than or equal to X, then the answer is YES. Otherwise, NO.

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

        So why did you suggested a complex O(nlog(n)) solution ?

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

          Why complex? Most two popular ways to get LIS either by binary search, or DP + segment trees. In fact, DP+ segment tree solution is easier to get to than the binary search, which requires more casework.

          → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    What does coordinate compression means? Google search hasn't got me anywhere.

    My solution for the LIS:

    let $$$a[i]$$$ be the length of LIS wich the last element is $$$i$$$

    then $$$a[i]$$$ = maximum of $$$a[0...i-1]+1$$$

    finding the maximum can be done using a fenwik tree or a segment tree. Is this different from your solution? If so can you explain me yours

    Edit: Oh it just occurred to me. we can't do this if maximum element is too large. I guess coordinate compression is to solve that issue?

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

      Yes, if element is too large, I just renumber it to smaller one. I renumber all elements from $$$0$$$ to $$$N-1$$$ in ascending order.

      → Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

I think if finding LIS of a sequence is lower-bounded by O(nlog(n)), we can prove that we can do no better than O(nlog(n)) in the worst case.

Assume X >= LIS of the sequence. So to check if this length is possible we have to do >= O(nlog(n)) work.

So in worst case O(nlog(n)) is the best we can do.

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

    Good thought, but this isn't a valid proof. There's plenty of problems where answering "is the answer bigger than or equal to X?" is faster than answering "what is the answer?". Since the latter can be obtained from the former using binary search, a correct lower bound, only knowing the fact that answering "what is the answer?" has a lower bound of $$$O(n \log n)$$$, is $$$O(\frac{n \log n}{\log n}) = O(n)$$$, but this ends up being useless here.

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

    Well technically checking whether the LIS is of length at least X could be faster than calculating the LIS. For example, the problem of checking whether a palindrome of length X exists in a string can be carried out in linear time with hashes, while a binary search + hashes solution takes $$$O(n \; log \; n)$$$ time to compute the longest palindrome. However, the longest palindrome can be computed in linear time with other methods (such as Manacher's algorithm or eertree).

    → Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

If $$$X \geq | LIS(A) | $$$ means there is such algorithm that find Longest Increasing Subsequence length in Linear. But currently there isnt and continue being researched by some researchers, the best I know is that some papers that prove such $$$O(n\ log(log(n)))$$$ algorithm exists but it is either/both complex or/and having big hidden constant to use in practical

→ Reply