No. 16 - Maximal Length of Incremental Subsequences

Problem: Given an unsorted array, find the max length of subsequence in which the numbers are in incremental order.

For example: If the input array is {7, 2, 3, 1, 5, 8, 9, 6}, a subsequence with the most numbers in incremental order is {2, 3, 5, 8, 9} and the expected output is 5.

Analysis: We try to get the maximum length of all increasing subsequences ending with each element in the array.

For instance, when we analyze the maximum length of all increasing subsequences ending with number 5, we compare it with each number before it. The first number 7 is greater than 5. If the subsequence comes from 7, 7 cannot be included into the subsequence. Therefore, its length is 1. The following three numbers 2, 3 and 1 in the input array before 5 are less than 5. If the previous number of 5 in the increasing subsequence is 2, the maximum incremental length is 2. If the previous number of 5 in the increasing subsequence is 3, the maximum incremental length is 3 (with number 2, 3, and 5) since the maximum length of all subsequences ending with number 3 is 2 (with number 2 and 3). Similarly, its maximum length is 2 if the previous number is number 1. The whole process can be summarized in Table 1.

	7	2	3	1	5	8	9	6
7	1	NA	NA	NA	NA	NA	NA	NA
2	1	1	NA	NA	NA	NA	NA	NA
3	1	2	1	NA	NA	NA	NA	NA
1	1	1	1	1	NA	NA	NA	NA
5	1	2	3	2	1	NA	NA	NA
8	2	2	3	2	4	1	NA	NA
9	2	2	3	2	4	5	1	NA
6	1	2	3	2	4	1	1	1

Table 1: Process to get the maximum length of increasing subsequences in array {7, 2, 3, 1, 5, 8, 9, 6}. Numbers in each row indicate length of subsequences ending with row title with previous number in the column title. Highlighted numbers with yellow background are the maximum lengths.  The highlighted number 5 with yellow background and red font is the maximum length of all incremental subsequences in the input array.

We are ready to write code with the detailed analysis above. The following is sample code:

int LengthOfIncreasing(int* data, int length)

{

    if(data == NULL || length < 0)

        return 0;

    int* longest = new int[length];

    longest[0] = 1;

    int max = 0;

    for(int i = 1; i < length; ++ i)

    {

        max = 0;

        for(int j = 0; j < i; ++ j)

        {

            if(data[j] < data[i] && longest[j] > max)

                max = longest[j];

        }

        longest[i] = max + 1;

    }

    max = 0;

    for(int i = 0; i < length; ++ i)

        if(longest[i] > max)

            max = longest[i];

                                                                  

    return max;   

}

Even though a 2-D matrix is needed to analyze the process, only a 1-D array is necessary in our code to store the maximum length of subsequences ending with each number in the input array.

If we are familiar with dynamic programming, we can get a direct solution quickly in a formal way. We can define a function f(i) indicating the maximum length of all subsequences ending with the i^th number in the input array (denoted as A[i]). We define another function g(i, j) which stands for the maximum length of incremental subsequences ending with A[i] coming from A[j]. The required output is max(f(i)) where 0<=i<n and n is the length of array. We can get f(i) with the following equation:

Actually, same code will be implemented based on this equation. The function f(i) is longest[i] in the code above. Therefore, it is identical to the previous solution.

The discussion about this problem is included in my book <Coding Interviews: Questions, Analysis & Solutions>, with some revisions. You may find the details of this book on Amazon.com, or Apress.
 

The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this ariticle in your blog or webpages,  please add a reference to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact me (zhedahht@gmail.com) . Thanks.