Saturday, February 16, 2013

The longest increasing subsequence problem

There was the following question on the RSDN site.
I have an array of size N. This array consists of numbers from 1 to N, and they are not repeated, and they are at random order. How can I determine the length of an maximum increasing sequence?

The longest increasing subsequence (LIS) problem is to find a subsequence of a given sequence in which the subsequence elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous, or unique. LIS is solvable in time O(n log n), where n is the length of the input sequence.

As a base, I took the algorithm from GeeksforGeeks site. I fixed few bugs in this algorithm and programmed it in C#.

  1.   class LongestIncr_ingSubseq
  2.   {
  3.     public Int32 LongestIncrSubseq(Int32[] sourceArray)
  4.     {
  5.       Int32  lengthSourceArray = sourceArray.Length;
  6.       Int32[] tailIndices = new Int32[lengthSourceArray];
  7.       Int32[] prevIndices = new Int32[lengthSourceArray];
  8.       Int32  maxLength = 1;
  9.  
  10.       tailIndices[0] = 0;
  11.       prevIndices[0] = -1;
  12.  
  13.       for (Int32 i = 1; i < lengthSourceArray; i++)
  14.       {
  15.         if (sourceArray[i] < sourceArray[tailIndices[0]])
  16.           tailIndices[0] = i;
  17.         else if (sourceArray[i] > sourceArray[tailIndices[maxLength - 1]])
  18.         {
  19.           prevIndices[i] = tailIndices[maxLength - 1];
  20.           tailIndices[maxLength++] = i;
  21.         }
  22.         else
  23.         { 
  24.           Int32 pos =
  25.            GetCeilIndex(sourceArray, tailIndices, -1, maxLength - 1, sourceArray[i]);
  26.           prevIndices[i] = tailIndices[pos - 1 < 0 ? 0 : pos - 1];
  27.           tailIndices[pos] = i;
  28.         }
  29.       }
  30.  
  31.       for (Int32 i = tailIndices[maxLength - 1],
  32.        j = maxLength, l = lengthSourceArray - 1; j > 0; i = prevIndices[i], j--)
  33.         tailIndices[l--] = sourceArray[i];
  34.       for (Int32 i = lengthSourceArray - maxLength, j = maxLength; j > 0; j--)
  35.         Console.WriteLine("LIS " + String.Format("{0} ", tailIndices[i++]));
  36.       return maxLength;
  37.     }
  38.  
  39.     Int32 GetCeilIndex(Int32[] sourceArray, Int32[] tailIndices, Int32 l, Int32 r, Int32 key)
  40.     { 
  41.       Int32 m;  
  42.       while( r - l > 1 )
  43.       {   
  44.         m = l + (r - l)/2;
  45.         if (sourceArray[tailIndices[m]] >= key) r = m;   
  46.         else l = m; 
  47.       }
  48.       return r;
  49.     }
  50.   }