How to find Max difference in a list/array in scala using recursion?

Question

I'm a beginner in Scala and I'm trying to solve a problem similar to this.

https://www.geeksforgeeks.org/maximum-difference-between-two-elements/

I have written the Scala version of the code written in that site. This is my code:

object stock{
def getMaxP(Li:List[Int]):Int={

var max_diff=Li(1)-Li(0)
var min_ele=Li(0)

for(i<-0 until Li.length){      
  if(Li(i)-min_ele>max_diff) max_diff=Li(i)-min_ele
  if(Li(i)<min_ele) min_ele=Li(i)
}

max_diff  
}

def main(args:Array[String]){
val li=List(10, 7, 5, 8, 11, 9)
println(getMaxP(li))
}

}

The above code works. But I want to solve it using recursion and I prefer to use the listname.tail function. I could pass s_p_y.tail to the recursive function (since s_p_y is a list) and solve it but I don't know how to implement that.

This is an example code I found online which uses recursion to find max element.

def max2(ints: List[Int]): Int = { 
@tailrec
def maxAccum2(ints: List[Int], theMax: Int): Int = {
  if (ints.isEmpty) {
    return theMax
  } else {
    val newMax = if (ints.head > theMax) ints.head else theMax
    maxAccum2(ints.tail, newMax)
  }
}
maxAccum2(ints, 0)
}

} 

Answer 1

The straight forward solution to this problem is to use methods made available from the standard library.

List(2,5,10,6,4,8,1).combinations(2).map{case List(a,b) => b-a}.max //res0 = 8

But as you are trying to use recursion, here's a recursive method that itself uses an inner recursive method.

// find the maximum difference between any 2 numbers in a List[Int]
// (always: laterNumber - earlierNumer)
def maxDiff(li: List[Int], mx: Int = Int.MinValue): Int = {

  // test all subsequent elements against the current head
  def loop(subList: List[Int], subMax:Int = mx): Int =
    if (subList.isEmpty) subMax
    else loop(subList.tail, subMax max subList.head - li.head)

  if (li.isEmpty) mx  //all done
  else maxDiff(li.tail, loop(li.tail))
}

Usage:

maxDiff(List(7, 9, 5, 6, 3, 2))  //res1: Int = 2

No var required.

Answer 2

Thank you for the answer @user unknown. This is how I solved the problem using your approach. Please let me know if I can improve my code in any way.

object stock {


  def getMaxp(li: List[Int], maxd: Int, min: Int): Int = li match {
    case Nil => maxd
    case x :: rest => {
      var lmaxd: Int = maxd
      var lmin: Int = min
      if (x-min > maxd) lmaxd = x - min
      if (x < min) lmin = x
      getMaxp(rest, lmaxd, lmin)
    }
  }


  def main(args:Array[String]){
    val li =List(10, 7, 5, 8, 11, 9)
    val min=li(0)
    val maxd=li(1)-li(0)
    println (getMaxp(li,maxd,min))
  }

}

Answer 3

A typical pattern is pattern matching on collections:

@annotation.tailrec
def getMaxp (li: List[Int], min: Int, dmax: Int): Int = li match {
    case Nil => dmax ???
    case x :: rest => getMaxP (rest, ???, ???)
}

def main(args:Array[String]){
    val li = List (10, 7, 5, 8, 11, 9)
    println (getMaxp (li, ???, ???))
}

What is in the empty case - which might be at end of list, or since the initial List is empty?

Param 2 and 3 for getMaxp have to somehow relate to min, max and x (li(0)).

You might call other functions, which you have to write of course, just in place, to avoid cluttering the space with intermediate values.

In real Life, to make calling the method convenient, you can provide an easy to call interface, and handle the starting phase inside and use an inner function, which ensures, chosing the right starting values:

def getMaxp (li: List[Int]): Int = li match {

    @annotation.tailrec
    def getMaxp (li: List[Int], min: Int, dmax:Int): Int = li match {
        case Nil => ???
        case x :: rest => getMaxP (rest, ???, ???)
    }
    getMaxP (rest, ???, ???)
}

def main(args:Array[String]){
    val li = List (10, 7, 5, 8, 11, 9)
    println (getMaxp (li))
}