Make delicious recipes!

Find Max-Increasing-Subsequence in an array

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]

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




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







Like us on Facebook to remain in touch
with the latest in technology and tutorials!


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

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal