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.   }

MMIXAL.NET

Soon professor Donald E. Knuth(from Stanford university) will publish fourth volume of The Art Of Computer Programming book. (To enlarge a picture click on it.)

A chapter devoted to MMIX language was already published as Fascicle 1. He wants to rewrite all programs in the series using MMIX.

Every student (or software programmer) who studies computer algorithms should know the MMIX language.

Donald E. Knuth invented the MMIX language and created an assembler, a simulator and a debugger for DOS-like operating systems.

The MMIXAL.NET project is based on the original work done by Donald E. Knuth.

MMIXAL.NET was designed to work with MMIXAL programs using the Microsoft.NET framework.

MMIXAL.NET project allows you to assemble, debug and simulate MMIXAL programs with a pleasure which MDI and GUI environments provide.

MMIXAL.NET was written in C# language. The hardware requirements are the same as for Microsoft.NET framework.

The project contains some interesting internals (besides an assembling, a simulating and a debugging as a general process ):

_ how to create Tab control from a set of Panel controls;
_ how to create advance console for Windows Forms;
_ how to number lines of RichTextBox control;
_ how to keep debugger's cursor synchronized with binary code and listing lines;
_ how to use Factory patterns and an inheritance to create different kind of Forms;
_ how to bind break points with binary code;
_ how to implement MDI interface for Windows Forms;
_ how to develop a search of regular expressions for RichTextBox control and internal structure to keep regular expressions as a collection;
_ how to implement double buffering technique to fight a flicker;
_ how to implement intellisense box for fast typing instruction's name;
_ how to use treap structure to organize virtual memory; how to keep it balance;
_ how to use a trie structure to organize symbol table;
_ how to develop a print engine to print opened files;
_ how to implement 64-bit integer arithmetic;
_ how to implement 64-bit floating point arithmetic in accordance with IEEE Standard 754;
_ how to structure the object file;

_ how to create a loader (a program which gets an object file into RAM in order to run it);

_ how to use global variables in C#;

_ how to serialize a state of MMIXAL.NET into a file and vise versa;

_ how to synchronize a simulation of the MMIX program with Windows Forms GUI.

To learn details about how to purchase the product or to report bugs or to make an enquiry send an email to peternik2010@yahoo.com.