Algorithms - Longest Increasing Subsequence in Swift

Subscribe to my newsletter and never miss my upcoming articles

Hello everyone, Leo here.

Today we'll explore one of the LIS problems. The longest increasing subsequence is a very classic problem of computer science and has various approaches. Today we'll exam the Dynamic Programming one because is very clean. 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

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. Of course 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 number 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 calculate the result for the first one, we have to check:

  1. Is the actual number bigger than the previous ones. 1.1 If no, go to the next number of the sequence 1.2 If yes, we need to calculate max between the cache of the old number + 1 and the actual response. But why we need that. Imagine that the actual number is bigger than various other past number, 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 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 x in 1..<list.count {
    for y in 0..<x {
        if list[x] > list[y] {
            cache[x] = max(cache[x], cache[y]+1) //  store the result value to use later 
        }
    }
}

print(cache.max() ?? 0)

This algorithm is O(nˆ2) because 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)

I hope you enjoy this algorithm and if you have any thoughts, critics or just a Hello, please comment below.

Thanks for the reading and... That's all folks.

Credit: image

No Comments Yet