gautam94's blog

Finding Longest Increasing Subsequence in O(nlogn) time
By gautam94, 11 years ago, In English

I am having trouble understanding the nlogn algorithm for solving the LIS problem. I have implemented the algorithm given here on page number 6. Link to CPP implementation. I think it's only checking the subsequence starting at index 0 so how is this algorithm correct? Or is my implementation wrong? Someone please help prove the correctness of this algorithm. Thanks.

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

Comments Comments (22)
| Write comment?
»
11 years ago, # |
  Vote: I like it +9 Vote: I do not like it

http://ideone.com/Vzvbyu

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

    OK thanks a lot for your help. I understood your solution and its really O(nlogn), but what about the one posted earlier? What's wrong with the implementation I provided?

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

      I think it should be st.erase(it) instead of st.erase(a[i])

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

        That was a really stupid mistake by me. Again thanks for your help.

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

          Also, if we are searching for non-decreasing longest sequence then your algorithm will not work correctly.

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

    The problem of this solutions is tracing. How can we get the result array?

    → Reply
»
11 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it 
vector<int> d;
int ans, n;
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        int x;
        scanf("%d", &x);
        vector<int>::iterator it = upper_bound(d.begin(), d.end(), x);
        if (it == d.end()) d.push_back(x);
        else *it = x;
    }
    printf("LIS = %d", d.size());
    return 0;
}

I think this will be helpful.

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

    It's non-decreasing subsequence, right? Not increasing one.

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

      yeah ur right, this is non-decreasing subsequence.
      but changing upper_bound to lower_bound fixes that! :)

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

    For Longest decreasing sub sequence, what changes needed in the code ?

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

    I think this is for longest non-decreasing subsequence right? And for LIS, we should use std::lower_bound and replace that element? isn't it? Just for confirmation? Thanks.

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

      Yeah, this is non-decreasing subsequence. And yes, using lower_bound instead of upper_bound would make it increasing.

      → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    set<int> st;
set<int>::iterator it;
st.clear();
for(i=0; i<n; i++)
{
st.insert(a[i]); it=st.find(a[i]);
it++; if(it!=st.end()) st.erase(it);
}
cout<<st.size()<<endl;

    This also works

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

I have a very short implementation:


  int n, a[N], b[N], f[N], answer=0;
  ... // enter n and a[] from keyboard

  for (int i=1; i<=n; i++){
      f[i]=lower_bound(b+1, b+answer+1, a[i])-b;
      maximize(answer, f[i]);
      b[f[i]]=a[i];
   }

   printf("%d\n", answer);

If you want to print the LIS:


   vector<int> T;

   int require = answer;
   for (int i=n; i>=1; i--)
   if (f[i]==require){
      T.push_back(a[i]);
      require--;
   }
   // then print T with reversed order
   int i=T.size();
   while (i--) printf("%d ", T[i]);
   printf("\n");
→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I've learned it from this video https://www.youtube.com/watch?v=S9oUiVYEq7E

It's very well explained. My code:

#include <stdio.h>

int a[10001], t[10001], n, l, i;

/**
a -> This is the input, is an array of integers
t -> Each position have the index of the last item in the ith LIS
l -> The last valid position of t
n -> Size of input a
**/

int ceil(int v)
{
    int init = 0, fin = l; ///Start and end for binary search
    while(init < fin-1)
    {
        int m = (init+fin)/2;
        
        if(a[t[m]] >= v)
            fin = m;
        else
            init = m;
    }

    if(a[t[init]] >= v)
        return init;
    return fin;
}

void lis()
{
    r[0] = 1;
    t[0] = 0;
    l = 0;

    for(i=1; i<n; i++)
    {
        if(a[i] > a[t[l]])
            l++, t[l] = i;
        else
            t[ceil(a[i])] = i;
    }
}
→ Reply