VBA – Longest Increasing Subsequence

The longest increasing sub sequence is a well-known problem in computer science, its Wikipedia page is translated into 9 languages. 🙂 Thus, as far as I am watching some programming and algorithms courses in the SoftUni, I have decided to try to implement the solution of this problem with VBA.

Why? That is a good question, which I cannot answer. Pretty much just to make sure that it can be done with it and in order to realize how the algorithm for this works.

vba

 

So what do we have? Pretty much in my example we have the following numbers:

arr_seq = Array(1, 2, -6, -5, -3, 23, 123, 3, 2, -23, -5, 54, 100, 200, 300, 1111, 23412, 3, 4, 5, 6, 7, 8, 9, 19, 65, 2)

And we should come up with a solution, giving us something like this:

imm

As you see, my solution for the longest increasing sub sequence is the one on the last one of the immediate window, starting with -6,-5 and finishing in 19,65.

What are the steps to achieve this – here it is a good idea to read the Wikipedia article, but just in case, I will try to summarize it:

  • We build additional two lists with the same length as our input list – arr_len and arr_pre.
  • In arr_len we write how many numbers, including the given one on that position make an increasing subsequence

E.g. – in my case arr_len looks like this:

As you see, in position 25 we have 13. This means, that if we use the number in position 25, we would have an increasing sub-sequence of 13 numbers.

  • In order to find out which number is after which, we write in arr_pre the previous numbers. In my case it is like this:

Thus, we see, that if we decide to build the sequence, using position 26, the previous number is held in position 4. And indeed – in position 26 we have “4” and in position 4 we have “-3”. -3 is the first number from right to left, which is smaller than 4. You would probably need to read this twice or three times and then test the code to get the idea 🙂

At the end, I get the biggest length and I build an array with the answers. I reverse the array (have built a function for that) and I print it.

I really hope that you enjoy it!

Here comes the VBA code:

Available also in GitHub here! 😀

About

VBA Developer

Tagged with: , , ,