Longest Increasing sub-sequence in Go & Python

code.md

Edit

The algorithms differ so it's unfair to compare them even though Go is still faster. This was called to my attention by opeispo :)

Golang

Memory: 2.4MB Time: 4ms

func lengthOfLIS(nums []int) int {
    n := len(nums)    

    if n < 1 {
        return 0
    }    
    
    if n == 1 {
        return 1
    }
    
    store := make([]int, n+1)
    
    for i := n; i >= 0; i-- {
        store[i] = 1
        for j := i+1; j < n; j++ {
            if nums[j] > nums[i] && 1 + store[j] > store[i] {
                store[i] = 1 + store[j] 
            }
        }
    }
    
    result := 0
    for _, number := range store {
        if number > result {
            result = number
        }
    }
    return result
}

Python

Our dear slow language. Memory: 145.3MB => Probably because we're using 0(n²) storage... It'll still be slower with O(n) space sha. Time: 3604ms

class Solution:
    def lengthOfLIS(self, arr: List[int]) -> int:
        arr.insert(0, float('-inf'))
        n = len(arr)
        dp = [[0 for i in range(n+1)] for j in range(n+1)]
        # for i in range(n):
        #     dp[i][n] = 0

        for j in range(n-1, 0, -1):
            for k in range(0, j):
                keep = 1 + dp[j][j+1]
                # print("Value of Keep: ", keep)
                skip = dp[k][j+1]
                if arr[k] >= arr[j]:
                    dp[k][j] = skip
                else:
                    dp[k][j] = max(keep, skip)
        return dp[0][1]

Bruhhh, python has changed since I last wrote it.

Bruhhh, python has changed since I last wrote it.

Haha lol! It hasn’t changed, it’s just typings that we’re added to the code above.