ologn_13's blog

Need help in finding Longest increasing sub-sequence(LIS)
By ologn_13, 12 years ago, In English

Hi guys!! I was solving the problem of finding LIS of a given sequence. I had built the code for getting the length of LIS but now i am a bit confused in finding a LIS(any one)...please tell the modifications which should be done in following code (or the algorithmic modification). Thanks!!

#include<iostream>
using namespace std;

int Binarysearch(int*a,int c,int d,int key)
{   if(d<=c)
    return c;
    if(a[(c+d)/2]<key)
    { c = (c+d)/2 + 1;
      return Binarysearch(a,c,d,key);
    }
    else{ d = d-(c+d)/2;
          return Binarysearch(a,c,d,key);
    }
}

int main()
{   cout<<"Size: ";
    int n;
    cin>>n;
    
    int a[n];
    for(int i=0;i<n;i++)
    cin>>a[i];
    
    int end[n];// Storing the end elements of the sequences formed till now.
    
    end[0] = a[0];
    int len = 1;
    
    for(int i=1;i<n;i++)
    {
      if(a[i]<end[0])
      { end[0] = a[i];
        continue;
      }
      else if(a[i]>=end[len-1])
           { end[len++] = a[i];
              continue;
           }
           else{
                 // Binary searh in end[] for smallest element greater than a[i]
                 int c = 0;
                 int d = len-1;
                 int j =  Binarysearch(end,c,d,a[i]);
                 end[j] = a[i];
                
                }
      
      }
      
      cout<<"Size of Longest Sequence:- "<<len<<endl;
      
      return 0;
}
Tags lis
  • Vote: I like it
  • -4
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
12 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it 
vector<int> d(n+1, INF);
for (int i = 0; i < n; i++) {
    *lower_bound(d.begin(), d.end(), a[i]) = a[i];
}
cout << (lower_bound(d.begin(), d.end(), INF) - d.begin());
→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    thanks!! but can i find a LIS using modifications in my code?? Is there any utilization of array end[] in it??

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

      I've already given you this link: https://sites.google.com/site/indy256/algo/lis_nlogn

      Main idea: you can see the array heaps. heaps[i] is the smallest possible last element of the LIS of length i. These elements form an increasing sequence, so we can process each element x[i] in O(log(n)) time using binary search. For each element in heaps we also save the information to restore the LIS itself: no[i] is the index of heaps[i] in the initial array x, and pred[i] is the index of the previous element in the LIS which ends with x[i].

      → Reply