Question

How to find the longest increasing not sorted subsequence (LIS) of a sequence of numbers in Go

Answer 1

package main

import (
    "fmt"
)

func longestIncreasingSubsequence(nums []int) int {
    numslen := len(nums)
    if numslen == 0 {
        return 0
    }

    length := make([]int, numslen)
    for i := range length {
        length[i] = 1
    }

    maxLength := 1

    for i := 1; i < numslen; i++ {
        for j := 0; j < i; j++ {
            if nums[i] > nums[j] {
                if length[i] < length[j]+1 {
                    length[i] = length[j] + 1
                }
            }
        }
        if maxLength < length[i] {
            maxLength = length[i]
        }
    }

    return maxLength
}

func main() {
    nums := []int{4, 5, 1, 10, 3, 9, 18, 19}
    
    fmt.Printf("Length of LIS: %d\n", longestIncreasingSubsequence(nums))
}



/*
run:

Length of LIS: 5

*/

 

70+ SQL courses for beginners and professionals