最长上升子序列（LIS）

习题 5：最长上升子序列（LIS）

题目：给定数组 [-3,-2,1,6,2,-7,5,8,-9,-8,-2,7,6,11,-2,3,-4]，求最长上升子序列的长度。

object LongAS {
  def main(args: Array[String]): Unit = {
    var a = List(-3, -2, 1, 6, 2, -7, 5, 8, -9, -8, -2, 7, 6, 11, -2, 3, -4)
    val n = a.length
    var f = Array.ofDim[Int](n)
    var ans = 0
    for (i <- 0 until n) {
      f(i) = 1
      for (j <- 0 until i) {
        if (a(i) > a(j)) {
          f(i) = math.max(f(i), f(j) + 1)
        }
      }
      ans = math.max(ans, f(i))
    }
    println(ans)
  }
}