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.
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:
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
0 --> 1 1 --> 2 2 --> 1 3 --> 2 4 --> 3 5 --> 4 6 --> 5 7 --> 4 8 --> 4 9 --> 1 10 --> 2 11 --> 5 12 --> 6 13 --> 7 14 --> 8 15 --> 9 16 --> 10 17 --> 5 18 --> 6 19 --> 7 20 --> 8 21 --> 9 22 --> 10 23 --> 11 24 --> 12 25 --> 13 26 --> 4 |
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
0 --> -1 1 --> 0 2 --> -1 3 --> 2 4 --> 3 5 --> 4 6 --> 5 7 --> 4 8 --> 4 9 --> -1 10 --> 2 11 --> 5 12 --> 11 13 --> 12 14 --> 13 15 --> 14 16 --> 15 17 --> 8 18 --> 17 19 --> 18 20 --> 19 21 --> 20 22 --> 21 23 --> 22 24 --> 23 25 --> 24 26 --> 4 |
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 |
Option Explicit Public Const NO_PREVIOUS = -1 Sub Main() Dim arr_seq As Variant Dim arr_len As Variant Dim arr_pre As Variant Dim lng_best As Long 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) ReDim arr_len(UBound(arr_seq)) ReDim arr_pre(UBound(arr_seq)) lng_best = CalculateLongestIncreasingSubsequence(arr_seq, _ arr_len, _ arr_pre) Call print_array(arr_seq) Call print_array(arr_len) Call print_array(arr_pre) Call PrintLongestIncreasingSubsequance(arr_seq, arr_pre, lng_best) End Sub Public Sub PrintLongestIncreasingSubsequance(ByRef arr_seq As Variant, _ ByRef arr_pre As Variant, _ lng_best As Long) Dim arr_result As Variant Dim l_counter As Long: l_counter = 0 ReDim arr_result(1) While (lng_best <> NO_PREVIOUS) ReDim Preserve arr_result(l_counter) l_counter = l_counter + 1 arr_result(l_counter - 1) = arr_seq(lng_best) lng_best = arr_pre(lng_best) Wend Debug.Print Join(reverse_array(arr_result), " ") End Sub Public Function CalculateLongestIncreasingSubsequence(ByRef arr_seq As Variant, _ ByRef arr_len As Variant, _ ByRef arr_pre As Variant) As Long Dim lng_best_len As Long: lng_best_len = 0 Dim lng_best_ind As Long: lng_best_ind = 0 Dim x As Long Dim i As Long For x = LBound(arr_seq) To (UBound(arr_seq)) Step 1 arr_len(x) = 1 arr_pre(x) = NO_PREVIOUS For i = 0 To x Step 1 If (arr_seq(i) < arr_seq(x)) And (arr_len(i) + 1 > arr_len(x)) Then arr_len(x) = arr_len(i) + 1 arr_pre(x) = i If arr_len(x) > lng_best_len Then lng_best_len = arr_len(x) lng_best_ind = x End If End If Next i Next x CalculateLongestIncreasingSubsequence = lng_best_ind End Function Public Sub print_array(ByRef my_array As Variant) Dim counter As Long For counter = LBound(my_array) To UBound(my_array) Debug.Print counter & " --> " & my_array(counter) Next counter Debug.Print "------------------------------" End Sub Public Function reverse_array(ByVal my_array As Variant) As Variant Dim counter As Long Dim counter_2 As Long Dim arr_new As Variant ReDim arr_new(UBound(my_array) + 1) For counter = LBound(arr_new) To UBound(arr_new) - 1 counter_2 = UBound(arr_new) - counter - 1 arr_new(counter) = my_array(counter_2) Next counter reverse_array = arr_new End Function |