Programming Interview 49: Print Longest Increasing Subsequence (LIS) using Dynamic Programming

Step by step to crack Programming Interview question 49: Print Longest Increasing Subsequence (LIS) using Dynamic Programming
e.g. (2,6,4,5,1,3), the LIS = (2,4,5)
Please notice: The increasing subsequence does not have to be contiguous.

Analysis:
1. One example of Dynamic Programming (DP):
1.1. Use additional memory to save the previous computation results, in order to save duplicate computation efforts.

Procedures:
1. Additional memory to be facilitated
1.1. An integer array: Longest increasing subsequence size ending with the current position
1.2. A char string array: Each stores the subsequence path ending

2. For each new position to be processed
2.1. Check all previous positions to see how to append the current position to make the increasing subsequence length the maximal
2.2. The current position value should be larger than previous one
2.3. The previous_Size+1 is larger than current size

Please note: this O(N^2) time-complexity DP solution is not the best time-efficient solution. Google the O(nLogn) solution yourself.

[AI_Edu_]

That's a good point. As to print all LIS, we need a collection data structure to store all the possible LIS for each position (ending at that position), other than just recording a single first-met LIS with longest length (which obviously ignore those cases that multiple LISs has same lengths just like you case). Usually the problem to print out the length that will be more suitable for an interview haha. Thanks again for pointing this out. Good point.

[souvikdas]

great explanation!! thanks a lot !!
btw what IDE are you using here(i.e for java) and for c++ programming?
Thanks again for the videos.... :)

[titombo]

Your code made me understand the solution of the wikipedia. Thanks!!!

Thanks, good one. A little bug indeed in the very last for loop ("finally go scanning again...")... but clear, simple solution to this problem, exactly what a good algo should be :-)

[zeeshanzahid]

Thanks .. Nice tutorial for beginners.

[moheetbhute]

paths[i] will store only one sequence ending in i. but there could be multiple sequences ending in i and of same length.

[AndrewJD]

Nice work, but this solution shows not all LIS but only several ones.
Consider following sequence {2, 4, 3, 5, 1, 7, 6, 9, 8}. There are 8 LIS but the solution shows only two.

[dmitryshifer]

As mentioned before- not all LIS covered in ans.

[Tatefootball]

why no sound? If I wanted to read the explaination, I wouldn't have gone to youtube.

[taraszubyk]

Actually, you have a bug in your implementation.
After DP part you go through size array, but your for-loop starts from 1, instead of 0.

P.S. Remember, copy/paste is a bad tool in coding ;)