Advertisement
Guest User

Untitled

a guest
Feb 25th, 2020
125
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.64 KB | None | 0 0
  1. def longestIncreasingSubsequence(s: Seq[Int]): Seq[Int] = {
  2. require(s.length > 0)
  3. val N = s.size
  4.  
  5.  
  6.  
  7. var d = Array.fill(N)(Array[Int](-1))
  8.  
  9. d(0)(0) = s(0)
  10.  
  11.  
  12. for( i <- 1 until N) {
  13. for( j <- 0 until i){
  14. if( (s(i) > s(j)) && (d(i).size < d(j).size + 1) ){
  15.  
  16. d(i) = d(j)
  17. }
  18.  
  19. }
  20.  
  21.  
  22. d(i) = d(i) :+ s(i)
  23. }
  24.  
  25.  
  26.  
  27. var max = d(0)
  28.  
  29. for (y <- d){
  30. if(y.size > max.size){
  31. max = y
  32. }
  33. }
  34. print(max.toSeq.filter(_ >= 0))
  35. print("\n")
  36. max.toSeq.filter(_ >= 0)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement