Given
an array of integers, find max-increasing-subsequence.

So,
in the following array {9, 15, 11, 3, 12, 10},
MIS is {9, 11, 12}

Solution:

Basic
approach here is that starting from any point in the array, you
should be able to check each and every other point. This approach
will cover all the possible paths and we need to find the biggest
path which is sorted.

If
mis
represents the length of maximum subsequence ending at k, then it can
be expressed recursively as mis(k) = 1 + mis(k-1) if arr[k] >
arr[k-1]

And
mis[0] = 1 since a single element can form a MIS of length 1.

Problem
with above is that it only takes contiguous locations into account.

For
a complete solution, we will need to consider all locations from 0 to
k-1 and choose the maximum among them.

So
mis(k) = max (

1
+ mis(k-1) if arr[k] > arr[k-1]

1
+ mis(k-2) if arr[k] > arr[k-2]

1
+ mis(k-3) if arr[k] > arr[k-3]

...

);

Programmatically,
it can be expressed as:

The
first call to this function finds maximum MIS-length for MIS ending
at last element of the array. But since the maximum MIS may not be
the one ending at the last element, we need to keep a global variable
which will find the maximum across all locations.

This
is where gMaxMis comes into picture.

By
the above logic, gMaxMis is set to max of MIS ending at all the
indices of the array and that is what we want.

Since
the above is a plain recursion and does not use DP, its running time
is exponential.

It
can be improved by using DP which will cache the result of previous
computations:

Order
for the above is O(n^2)

If
we also have to return the actual MIS instead of just the MIS-length,
then we can use an auxiliary array to store the index of the previous
node in the MIS ending at that index.

The
code for the same can then be written as:

int [] findMaxIncreasingSubseq (int arr[])
{
int misLengths [arr.length] = {1};
// initialized to 1 because each element is MIS of length itself
int misPrevNodeIndices [arr.length] = {-1};
for (int i=1; i<arr.length; i++)
{
int nextEle = arr[i];
int misPrevNodeIndex = -1;
for (int j=0; j<i; j++)
{
if (nextEle > arr[j])
{
if (misLengths[j] + 1 > misLengths[i])
{
misLengths[i] = misLengths[j] + 1;
misPrevNodeIndex = j;
}
}
}
misPrevNodeIndices[i] = misPrevNodeIndex;
}
int indx = findIndexOfMaxInArray (misLengths);
int maxMisLen = misLengths[indx];
int misSubseq [maxMisLen];
int pos = maxMisLen-1;
while (indx >= 0)
{
misSubseq[pos] = arr[indx];
indx = misPrevNodeIndices[indx];
pos--;
}
return misSubseq;
}

nLog(n) solution to find the MIS

Suppose MIS was found by creating all the increasing subsequences and then finding the longest one among them.

Step 1
If the array had only one element, then there is only one subsequence.

Step 2
If the array had two elements, then maximum number of increasing subsequences can be 2.
For example, if array = [1,9], then increasing subsequence is only [1,9]
But if array = [9,1], then increasing subsequences are [9] and [1]

Step 3
Now if another element '5' is added, increasing subsequences for the above two examples are: Example 1:
[1,9,5] -- subsequences -- > [1,9], [1,5] (i.e. a new sequence has forked from [1,9])
But we can safely omit [1,9] out of these two since [1,5] always has better
chances of fitting into longest subsequence than [1,9]

Example 2:
[9,1,5] -- subsequences -- > [1,5] (i.e. subsequence [9] is dropped and [1] is extended to [1,5])

Step 4
Let us add another element '7' to our two arrays. Example 1:
[1,9,5,7] -- subsequences -- > [1,5,7] Example 2:
[9,1,5,7] -- subsequences -- > [1,5,7]

Step 5 Example 1:
[1,9,5,7,3] -- subsequences -- > [1,5,7] and [1,3] Example 2:
[9,1,5,7,3] -- subsequences -- > [1,5,7] and [1,3]

We have to consider [1,3] here alongside [1,5,7] because it is possible that future numbers may all be between 3 and 7.
If that happens, then subsequence [1,3] will become part of MIS and [1,5,7] will remain at length 3.

Step 6
[1,9,5,7,3,6] -- subsequences -- > [1,5,7] and [1,3,6]

Observation: If we only keep the ends of increasing subsequences, then just one pass of the array
should be sufficient to find the MIS.

/**************************************************
Using binary search on a sorted array, finds the
lowest number greater than the given key
**************************************************/
int findCeilIndex(int A[], int l, int r, int key)
{
while( r - l > 1 )
{
int mid = l + (r - l)/2;
if (A[mid] >= key)
r = mid;
else
l = mid;
}
return r;
}
/**************************************************
Finds Maximum Increasing Subsequence in
the given array in nLog(n) time.
**************************************************/
int findMIS (int A[], int size)
{
if (size <= 1)
return size;
int subseqTails[] = new int[size];
int misLen = 1;
// First number starts the first MIS.
// End of that MIS is A[0] and that first end is stored here
subseqTails[0] = A[0];
// subsequent numbers may start new MIS or fork existing ones
// We just maintain the ends of all such subsequences.
for( int i = 1; i < size; i++ )
{
if( A[i] < subseqTails[0] )
subseqTails[0] = A[i]; // .... case 1
else if ( A[i] > subseqTails[misLen-1] )
subseqTails[misLen++] = A[i]; // .... case 2
else
{
int ceilIndex = findCeilIndex (subseqTails, -1, misLen-1, A[i]);
subseqTails[ceilIndex] = A[i]; // .... case 3
}
}
// At this point, subseqTails does not contain the MIS itself
// It just contains the ends of all the subsequences considered
return misLen;
}

Example execution of the code:
Lets run the above code on the following array: [3, 5, 9, 1, 2, 6, 8, 10, 4]

subseqTails grows as follows:
[3]
[3, 5] // case 2
[3, 5, 9] // case 2
[1, 5, 9] // case 1
[1, 2, 9] // case 3
[1, 2, 6] // case 3
[1, 2, 6, 8] // case 2
[1, 2, 6, 8, 10] // case 2
[1, 2, 4, 8, 10] // case 3

Length of MIS = 5
Also, note that 'subseqTails' does not contain the MIS itself

Got a thought to share or found a bug in the code? We'd love to hear from you: