## Saturday, October 29, 2011

### 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 = 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 ith 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.

1. Hello, I am wondering why do you even need this 2-D matrix, when this problem can be solved using just one-dimensional arrays? Isn't it a memory overhead?

Please see my C# code without 2D arrays below

var a = new int[] { 7, 2, 3, 1, 5, 8, 9, 6 };
var b = new int[a.Length];
var prev = new int[a.Length];
var maxLength = 0;
var maxIndex = -1;

b = 1;
prev = -1;

for (int i = 1; i < a.Length; i++)
{
b[i] = 1;
prev[i] = -1;

for (int j = 0; j < i; j++)
{
if (a[i] > a[j] && b[j] + 1 > b[i])
{
b[i] = b[j] + 1;
prev[i] = j;
}
}

if (b[i] > maxLength)
{
maxLength = b[i];
maxIndex = i;
}
}

var sb = new StringBuilder();
var currentIndex = maxIndex;

while (currentIndex != -1)
{
sb.Insert(0, a[currentIndex] + " ");
currentIndex = prev[currentIndex];
}

Console.WriteLine("Max length = {0}", maxLength);
Console.WriteLine(sb.ToString().Trim());

And thanks for the blog, btw :)

2. 3. just FYI, there is an algorithm that solves LIS in O(nlogn) time and O(n) space, check it out on wiki http://en.wikipedia.org/wiki/Longest_increasing_subsequence#Efficient_algorithms

4. Note that the example completely changes the problem. The use of the word 'sequence' is incredibly misleading; you're actually looking for SUBSETS starting at the ith node, not SEQUENCES. Finding sequences is trivial (simply walk the array tracking the longest sequential series of increasing numbers). When the problem becomes about SUBSETS, it becomes much more complicated.

5. ... you also have a memory leak.

6. Yes, the word subsequence is misleading

7. Java Program with O(n) - Single for loop without 2D matrix

import java.util.List;

public class FindMaxLengthIncrementalArray {

/**
* @param args
*/
public static void main(String[] args) {
/*
* 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
*/
int[] array = { 7, 2, 3, 1, 5, 8, 9, 6 };
int max = -1;
for (int i = 0; i < array.length - 1;) {
System.out.println(subList);
if (array[i] > max && array[i] < array[i + 1]) {
max = array[i + 1];
i += 2;
} else if (array[i] > max && ((i + 1) == (array.length - 1))) {
break;
} else
i++;
}
System.out.println(subList);
}
}

1. Hey Edwin, your algorithm only works with some (very limited) subsets, not to be harsh but you missed a lot of possibly good inputs in it. You shouldn't be comparing two elements at a time, or at least you need more cases. What about an element that you should take, that is in front of an element that is very large, i.e. {1, 10, 2, 3, 4}? Your algorithm would take return 2, for the set {1, 10}.
You also are failing to account for sequences that may be desirable but very spread out as well. For instance an input array that yours would not work with is this: {7, 2, 3, 1, 5, 4, 8, 5, 9, 6, 7 }. You can't actually do a O(n) solution to this, best is O(nlogn).

8. I can write O(1) without auxiliary memory
//No. 16 - Maximal Length of Incremental Subsequences
int MaxLength(int []arr)
{
int maxL = 1;
int maxC = 1;
for(int i = 1;i < arr.Length;i ++)
{
if(a[i] > a[i - 1])
{
maxC ++;
}
else
{
maxL = maxC > maxL ? maxC : maxL;
maxC = 1;
}
}
return maxL;
}

9. This comment has been removed by the author.

10. This is a "C" code. Works fine though.

#include
#include
void main()
{
int ar={7,2,3,1,5,8,9},i,j,max=0,c=0;
clrscr();
for(i=0;i"<"6;i++)
{ c=1;
for(j=i+1;j"<"7;j++)
{
if(ar[i]"<"ar[j])
c++;
}
if(c">"max)
max=c;
}
printf("%d",max);
getch();
}

11. import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.*;
import java.io.*;
class enterclass
{
public static void main(String[] args) throws Exception
{
int N=Integer.parseInt(line);
int arr[]=new int[N];
int i=0;
while(i!=N)
i++;
}
Arrays.sort(arr);
int count[]=new int[N];
int j=0;
for(int y=0;y<N;y++){count[y]=1;}
int m=0;
int a=arr[j];
for(int l=1;l<N;l++)
{a=a+l;
for(int k=0;k<N;k++)
{if(arr[k]==a)
{++count[j];
break;}
else if(k==N-1){
if(j<N-1)
{a=arr[j++];

l=0;}}
}
}

Arrays.sort(count);
System.out.println(count[N-1]+1);

}
}

12. this code is proper work for any number of size of array...u can easily find out Maximal Length of Incremental Subsequences...it's dyanamic algorithm

13. 14. Hi,
Does i make sense to use DP when we can traverse a "unary tree" i.e. the recursion has only on linear branch, and no bifurcations?

public static int maxLenght(int[] arr) {
return fml(arr, 0, Integer.MAX_VALUE,0, 0);
}

private static int fml(int[] arr, int idx, int last, int lenght, int maxReached) {
if (idx == arr.length) {
if (lenght > maxReached) {
maxReached = lenght;
}
return maxReached;
}

if (last > arr[idx]) {
if (lenght > maxReached) {
maxReached = lenght;
}
lenght = 1;
}

return fml(arr, idx + 1, arr[idx], lenght + 1, maxReached);
}

15. Hey Brother,

Best thing I have read in a while on this #topic. There should be a standing ovation button. This is a great piece.

When creating a crawler that reads from S3, it would be nice if you could specify the Athena table name. At the moment it takes the name of the S3 folder it crawls.

By the way do you have any YouTube videos, would love to watch it. I would like to connect you on LinkedIn, great to have experts like you in my connection (In case, if you don’t have any issues).

Shukran,

16. Hi Buddie,

What you’re saying is absolutely correct No. 16 - Maximal Length of Incremental Subsequences, but this isn’t the exact situation everywhere. Where most smart folk work on a project - why can’t you do this the Boss asks :).

I have posted a few times a issue about a couple of resources in my account which can not be deleted through AWS Management Console. No answer up to now.

Thank you very much and will look for more postings from you. AWS Training USA

Ajeeth

17. Hey There,

Best thing I have read in a while on this blog There should be a standing ovation button. This is a great piece.

When creating a crawler that reads from S3, it would be nice if you could specify the Athena table name. At the moment it takes the name of the S3 folder it crawls.

I started using this AWS Training USA blog for my training practice
By the way do you have any YouTube videos, would love to watch it. I would like to connect you on LinkedIn, great to have experts like you in my connection (In case, if you don’t have any issues).

Shukran,
Morgan

18. Hi Buddie,

I’ve often thought about this No. 16 - Maximal Length of Incremental Subsequences. Nice to have it laid out so clearly. Great eye opener.

Sorry if this is a stupid question, but I signed up my company for an AWS account. The traditional AWS homepage dashboard is not there in my new account. Instead I have "Shortcuts and Recently Viewed Services" and a few bigger icon shortcuts. AWS Tutorial

Super likes !!! for this amazing post. I thinks everyone should bookmark this.

Gracias
Ajeeth

19. SelamatPetang,

Interesting piece!Great to see someone write No. 16 - Maximal Length of Incremental Subsequences. who is not a fanatic or a complete skeptic. AWS Training USA

But now it was not letting me use the forum without putting a new nickname and new email address. Everytime I was putting my original nickname udasxilinx it was saying nickname is already used. But this does not make sense, because the nickname is used by me and I am using same email to login. Also it is not letting me use my actual email id when I used in as forum email. So I am forced to use a different nickname (udayxilinx) and different email address (uday.das@gmail.com) though from the root I am using the same old company's email id.

By the way do you have any YouTube videos, would love to watch it. I would like to connect you on LinkedIn, great to have experts like you in my connection (In case, if you don’t have any issues).

Regards,
20. 21. 22. 23. 