Dynamic Programming: Longest Increasing Subsequence (LIS)TiagoBlockedUnblockFollowFollowingFeb 2This article will walk you through how to solve another classic DP problem: Longest Increasing Subsequence (LIS).
To make it a bit more fun, we are going to pick another problem from the UVA¹ database: Strategic Defence Initiative².
Read that problem first before continuing this article.
In short, the problem states that there are some enemy missiles heading your way and you are equiped with a missile system to intercepting them.
For every missile you launch, the next one can only be launched higher than the previous one (because of a flaw in your missile system).
Your task is to write a program to find the maximum amount of enemy missiles that can be intercepted using your missiles, as well as printing out exactly which enemy missiles will be hit.
Here is an example:The number bellow each missile is its height.
We can write it down as an array:enemyMissileHeights = [2, 5, 1, 3, 4, 8, 3, 6, 7]What we want is the Longest Increasing Subsequence of enemy missiles to hit.
Notice that your subsequence does not need to be continuos.
Skipping some elements (in this problem, some enemy missiles) will usually give you a longer sequence (which is what we are looking for).
Spoiler alert: the Longest Increasing Subsequence of this example is: 2, 3, 4, 6, 7.
You can try solving this problem using Brute Force but that would yield you an exponential time solution.
It is easy to prove that.
Let’s say you have a program that goes through all possible subsequences in order to find out which one is the largest.
Notice that, for any given item in the original array, that item would either be in the sub-sequence or it would not.
Therefore, we have 2 possible states for each item (enemy missile).
Assuming we have ‘n’ enemy missiles and each one can be in 2 states (they either are in the sub-sequence or they are not), we have 2ⁿ possible subsequences to visit (this is also known as the powerset³).
Therefore, that solution would have a O(2ⁿ) complexity, way too slow for any decent-sized sequence.
The particular UVA problem we are solving does not give you the maximum size of ‘n’ (a mistake from their end) but through some trial and error, I found out they expect your program to work for sequences of up to 1000 items.
2¹⁰⁰⁰ = 10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376 possible subsequencesClearly we need a better approach.
Let’s define a few things first.
Let a[1.
n] be our original enemyMissileHeights array, i.
e, each value inside this array contains the height of a missile.
In our example this would be:a[1] = 2a[2] = 5a[3] = 1a[4] = 3a[5] = 4a[6] = 8a[7] = 3a[8] = 6a[9] = 7Let LIS[k] be the Longest Increasing Subsequence of a[1.
k], for 1≤k≤n.
Notice our goal is to find LIS[n].
Let’s follow the induction approach to solve DP problems I wrote in my first article⁴.
The first step is to find our induction hypothesis.
Let’s assume that, for a given sub-array a[1.
m] (1≤m<n), we already know what the size of the largest increasing subsequence for all arrays a[1.
k] (1≤k≤m) are.
In other words, we assume we know what the values of LIS[1], LIS[2],…,LIS[k] are.
This is our hypothesis.
Now, let’s append one new item to the original array ‘a’, ie, let’s add a[m+1].
We now have the array a[1.
m+1].
How do we find LIS[m+1] (knowing we already have LIS[k] for 1≤k≤m)?.All we have to do is find the largest LIS[k] such as a[k] < a[m+1] (because the next missile has to go higher than any previous one).
If no such ‘k’ exists that satisfies the previous inequality, that means a new longest increasing subsequence is starting in a[m+1] and therefore LIS[m+1] = 1.
Our induction hypothesis is completed.
Let’s now go to step 2, ie, find our base case:We know that LIS[1] = 1 (because there is only one item in the array a[1.
1] = a[1] = 2) and therefore that item must also be the Longest Increasing Subsequence).
Notice we are storing how many items are in the longest increasing subsequence in the LIS array, not the value of the item itself (2 in this case).
That is why LIS[1] = 1 and not 2.
With the base case done and the recursive formula found, we can finally code the heart of our program:After the above is processed, we will have our answer in LIS[n].
Notice the complexity of this algorithm is just O(n²), way better than the brute force approach.
So far we have found how long the Longest Increasing Sequence of the array a[1.
n] is.
Again, that value is inside LIS[n].
The UVA problem also asks us to print the sequence itself.
That is pretty easy to achieve though.
There are many ways to do it.
In my full code solution⁵ I chose to keep track of the parent of each item that make up the Longest Increasing Subsequence in a new array (parent[1.
n]).
For instance, in our example this is what the parent array would look like in the end:parent[1]: -1 //No parentparent[2]: 1parent[3]: -1 //No parentparent[4]: 1parent[5]: 4parent[6]: 5parent[7]: 1parent[8]: 5parent[9]: 8To find the final path, we just need to keep track of the index of the latest item that is inside the largest LIS we found.
Let’s call that variable lastIndexOfLargestLis.
Then we just need to do lastIndexOfLargestLis = parent[lastIndexOfLargestLis] until we reach the end of the sequence (i.
e, until parent[lastIndexOfLargestLis] == -1).
In the end you will get the index sequence in reverse order.
You can then invert the sequence however you want.
In my code I simply used the .
reverse() method available in the implementation of stl::list.
You can find my full C++ implementation here⁵.
Sources:UVA’s problem set index: https://uva.
onlinejudge.
org/index.
php?option=com_onlinejudge&Itemid=8“Strategic Defense Initiative”: https://uva.
onlinejudge.
org/index.
php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=438Powerset definition: https://en.
wikipedia.
org/wiki/Power_set“Dynamic Programming: An induction approach”: https://medium.
com/@tiagot/dynamic-programming-an-induction-approach-b5c5e73c4a19Complete solution: https://github.
com/TheCoinTosser/Competitive-Programming/blob/master/UVA/497__Strategic_Defence_Initiative.
cpp.