gautam94's blog

By gautam94, 4 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  

»
4 years ago, # |
  Vote: I like it +9 Vote: I do not like it
  • »
    »
    4 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?

    • »
      »
      »
      4 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])

      • »
        »
        »
        »
        4 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.

        • »
          »
          »
          »
          »
          3 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.

  • »
    »
    4 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?

»
4 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.

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

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

    • »
      »
      »
      4 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! :)

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

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

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

    so helpful code

  • »
    »
    4 months 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.

  • »
    »
    4 months 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

»
4 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");
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This can also be achieved with segment trees, though the code will be slightly longer because of the update and query functions.

»
22 months 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;
    }
}