Solved

longest increasing/decreasing subsequence in O( n * lg n )

Posted on 2004-09-04
8
479 Views
Last Modified: 2012-06-21
i need two algorithms. one that will calculate the LIS and one that will calculate LDS each in O( n * lg n ) from a vector<int> of numbers. i know the basic algorithm is

for i = 1 to n{
 bsearch L for largest L(a) < xi;
 L(a + 1) = Xi;
 }

where L is a list of numbers. the problem im having is printing out the subsequence.
0
Comment
Question by:Kitty__Kong
  • 4
  • 3
8 Comments
 
LVL 3

Expert Comment

by:kumvjuec
ID: 11983638
For this, you have to keep two variables which store indexes of the start and end element of the longest sequence found so far.

Strictly Increasing longest sequence--

lstart = lend = start = end = 0;
for (int i=0; i<size-1; i++)
{
  if (array[i+1] > array[i])
    end = i+1;
  else
    start = i+1;
  if (lend - lstart < end - start)
    { lstart = start; lend = end; }
}
0
 
LVL 11

Expert Comment

by:bcladd
ID: 11984799
kumvjuec's solution is O(n) and it works. Unfortunately it solves the wrong problem. It finds the longest increasing _sequential_ subsequence. That is, it finds the longest increasing run in the original array. When this problem is given in algorithms the problem is to find the longest subsequence where subsequence is a set of numbers from the original sequence IN THE SAME ORDER AS IN THE ORIGINAL but without regard to numbers BETWEEN them in the original sequence.

Kitty__Kong: In case there is any question, the same algorithm will solve both of your problems with the reversal of a single > or < sign.

What do you have so far? That is, what data structures are you using to support your solution? You can store the list of numbers as a vector<int> of the indices. To append a number to a list you just use push_back.

This is a fun problem with a lot of learning potential.

-bcl
0
 
LVL 1

Author Comment

by:Kitty__Kong
ID: 11985299


int bs( vector< pair<int, int> > &L, int s, int f, int t )
{
      int      m;

      if( s > f )
      {
            while( s >= L.size() || L[s].first >= t )
                  s--;

            return s;
      }

      m = (s + f) / 2;

      if( L[m].first > t )
            return bs( L, s, m - 1, t );
      else if( L[m].first < t )
            return bs( L, m + 1, f, t );
      else
      {
            while( L[m].first == t )
                  m--;

            return m;
      }
}

vector<int> Proc( vector<int> &nums )
{
      int                                          i, a;
      vector< pair<int, int> >      L;
      vector<int>                              ret;

      //reverse( nums.begin(), nums.end() );

      L.reserve( nums.size() );

      L.push_back( pair<int, int>( INT_MIN, INT_MIN ) );

      for( i = 0; i < nums.size(); ++i )
      {
            a = bs( L, 0, L.size() - 1, nums[i] );

            if( a + 1 >= L.size() )
                  L.push_back( pair<int, int>( nums[i], L[L.size() - 1].first ) );
            else
            {
                  L[a + 1].first = nums[i];
                  //L[a + 1].second = L[a].first;
            }

            for( int j = 0; j < L.size(); ++j )
                  cout << L[j].first << " ";

            cout << endl;
      }

      /*L.pop_back();
      reverse( L.begin(), L.end() );*/

      L.erase( L.begin() );

      for( i = 1; i < L.size(); ++i )
            ret.push_back( L[i].second );

      ret.push_back( L[L.size() - 1].first );

      return ret;
}

this is what i have so far. the problem is i dont understand how to keep track of each numbers predecessor which im trying to do in the second member of the pair<int, int>
0
Free Tool: IP Lookup

Get more info about an IP address or domain name, such as organization, abuse contacts and geolocation.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

 
LVL 11

Expert Comment

by:bcladd
ID: 11985318
(1) Do you have notes on the data representation? I am assuming that someone gave it to you and you are trying to use it. A quick description of what L is supposed to contain (and why you are comparing the result of bs+1 to the length of L in Proc) would save me some head pounding.

-bcl
0
 
LVL 1

Author Comment

by:Kitty__Kong
ID: 11985527
0
 
LVL 11

Expert Comment

by:bcladd
ID: 11986683
What predecessor are you keeping? That is, how are you encoding the sequence itself? L is related to the BEST subsequence of any given length. You will not be able to walk it to find the sequence (in particular, consider a sequence that ends with its second smallest value. In that instance L[2] will be replaced on the last iteration through the loop. Thus the predecessor of L[3] will have no predecessor available. I am pretty sure you're going to need more storage than they use in the agorithm you point to. Keeping each subsequence should not be too costly since you will only ever extend one by a single value. That would make L a vector<pair<int, vector<int> > instead of what you have.

I could be wrong. It has been a while since I taught this problem but I am pretty sure to get the actual sequence (rather than the length of the sequence) requires more storage.

-bcl
0
 
LVL 1

Author Comment

by:Kitty__Kong
ID: 11987239
this is where im stuck. when i add an item to L how do i know what its predecessor is? i had tried using a vector<pair<int, vector<int> > but couldnt figure out what to insert in the vector in the pair.
0
 
LVL 11

Accepted Solution

by:
bcladd earned 250 total points
ID: 11989853
Okay: When you add a new element to L, whereever it is, at THAT MOMENT you are extending the sequence in L[a] in L[a+]. That means that the CURRENT sequence in L[a] can be extended into L[a+1]

Right after updating L[a+1] (the if statement in Proc) you could use something like:

L[a+1].second = L[a].second;
L[a+1].second.push_back(L[a+1].first);

What does this do? It copies the sequence, of length a, into the a+1 slot in L and then extends it with the number that extends it.

Does this make sense? This way, if L[a] is changed in some way then the L[a+1]'s sequence is still what it was.

-bcl

0

Featured Post

Free Tool: Subnet Calculator

The subnet calculator helps you design networks by taking an IP address and network mask and returning information such as network, broadcast address, and host range.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

This article will show you some of the more useful Standard Template Library (STL) algorithms through the use of working examples.  You will learn about how these algorithms fit into the STL architecture, how they work with STL containers, and why t…
C++ Properties One feature missing from standard C++ that you will find in many other Object Oriented Programming languages is something called a Property (http://www.experts-exchange.com/Programming/Languages/CPP/A_3912-Object-Properties-in-C.ht…
The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…
The viewer will be introduced to the member functions push_back and pop_back of the vector class. The video will teach the difference between the two as well as how to use each one along with its functionality.

829 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question