Question

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

Answer 1

object LongestIncreasingSubsequence {
  def lis(nums: Seq[Int]): Int = {
    if (nums.isEmpty) return 0

    val length = Array.fill(nums.length)(1)
    var maxLength = 1

    for (i <- 1 until nums.length) {
      for (j <- 0 until i) {
        if (nums(i) > nums(j)) {
          length(i) = math.max(length(i), length(j) + 1)
        }
      }
      maxLength = math.max(maxLength, length(i))
    }

    maxLength
  }

  def main(args: Array[String]): Unit = {
    val nums = Seq(4, 5, 1, 10, 3, 9, 18, 19)
    
    println(s"Length of LIS: ${lis(nums)}")
  }
}




/*
run:

Length of LIS: 5

*/

 

70+ SQL courses for beginners and professionals