Hello everyone, Leo here. Today we’ll explore one of the Longest Increasing Subsequence in Swift, also known as LIS problems.

The LIS is a very classic problem of computer science and has various approaches.

Today we’ll examine the Dynamic Programming approach because it is very straighforward. Remember the dynamic programming solution is NOT the optimal solution, for that you will need to learn the famous patience sort (yep from the patience game inspired) or you can just go here and learn the solution in O(N log N).

No more talking, let’s go.

Problem – Longest Increasing Subsequence in Swift

The Longest Increasing Subsequence problem is to find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order. The result subsequence can be non continous relative to the original sequence. Ex: the answer to this list [1,3,2,3,1,5] is 4.

With dynamic programming, we can store the result of past iterations, this way we don’t need to recalculate past results increasing the algorithm speed. This comes with a space trade-off because we need auxiliary structures to do that. But is a very interesting technique to learn.

In this problem, we start with an N-sized list full of numbers 1. This is already one solution to the question because if there’s no increasing number, the answer for the longest subsequence length is 1.

let list = [1,5,3,1,7,9,3,6,10,2,22]
var cache = Array.init(repeating: 1, count: list.count) // our auxiliary structure full of one's

Now for starting with the second item, because we don’t need to calculate the result for the first one, we have to check:

  1. Is the actual number bigger than the previous ones?
    1. If no, go to the next number of the sequence
    2. If yes, we need to calculate the max between the cache of the old number + 1 and the actual response.

But why do we need that? Imagine that the actual number is bigger than various other past numbers, you can add plus 1 every time because this is not taking into consideration the cached result. So we have to compare the cached results to actually use dynamic programming and to give the right answer.

And the final algorithm looks like this, you can try it yourself in the playgrounds.

let list = [1,5,3,1,7,9,3,6,10,2,22]
var cache = Array.init(repeating: 1, count: list.count)

for current in 1..<list.count {
    for old in 0..<x {
        if list[current] > list[old] {
            cache[current] = max(cache[current], cache[old]+1) // store the result value to use later
        }
    }
}

print(cache.max() ?? 0) 

 

Small optimization

This algorithm is O(nˆ2) because of the nested for loop. And we can do a little improvement to the *cache.max* that is O(n). We can guard the max result along the way so we don’t need to traverse the cache again. The code could be something like:

let list = [1,5,3,1,7,9,3,6,10,2,22]
var cache = Array.init(repeating: 1, count: list.count)
var maxResult = 1

for x in 1..<list.count {
    for y in 0..<x {
        if list[x] > list[y] {
            cache[x] = max(cache[x], cache[y]+1)
            if cache[x] > maxResult {
                maxResult = cache[x]
            }
        }
    }
}

print(maxResult) // O(1)
cache.max() // O(n) 

And we are done!

 

Algorithms: Continue Studying

Merge sort is the definition of “a classic algorithm”. And if you are curious about how to implement that in Swift, you can check it here. There were evolutions through time in this algorithm, but the idea of divide and conquer is still the same.

Studying algorithms is sometimes really interesting. I found that you can solve an algorithmic problem using the Swift’s Set language feature. Check how to find the symmetric difference using pure Swift language.

 

Summary – Longest Increasing Subsequence in Swift

Today we check a dynamic programming solution to an ancient problem. I would like to hear from you what you think about this solution and how would you approach this problem.

That’s all my people, I hope you liked reading this article as much as I enjoyed writing it. If you want to support this blog you can Buy Me a Coffee or leave a comment saying hello. You can also sponsor posts and I’m open to freelance writing! You can reach me on LinkedIn or Twitter and send me an e-mail through the contact page.

Thanks for the reading and… That’s all folks.

Credits – image