Question

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

Answer 1

fun longestIncreasingSubsequence(nums: List<Int>): Int {
    if (nums.isEmpty()) return 0

    val length = MutableList(nums.size) { 1 }
    var maxLength = 1

    for (i in 1 until nums.size) {
        for (j in 0 until i) {
            if (nums[i] > nums[j]) {
                length[i] = maxOf(length[i], length[j] + 1)
            }
        }
        maxLength = maxOf(maxLength, length[i])
    }

    return maxLength
}

fun main() {
    val nums = listOf(4, 5, 1, 10, 3, 9, 18, 19)
    
    println("Length of LIS: ${longestIncreasingSubsequence(nums)}")
}



/*
run:

Length of LIS: 5

*/

 

70+ SQL courses for beginners and professionals