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.

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:

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:

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:

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

Available also in GitHub here! 😀

VBA – Longest Increasing Subsequence

Related posts: