What is the functional approach to solving the Longest Increasing Subarray problem in Scala?

edit

The functional approach to solving the Longest Increasing Subarray problem in Scala would involve using functional constructs like map, reduce, filter, and recursion to solve the problem.

Here's a possible solution:

1. Define a function called lis that takes an array arr as input and returns the length of the longest increasing subarray in arr.

2. Define an inner function called helper that takes three parameters:

   a. prev: the value of the previous element in the subarray b. len: the length of the current increasing subarray c. remaining: the remaining elements in the array to process

3. If remaining is empty, return len.

4. If prev is not defined (i.e. this is the first element in the subarray), call helper recursively with the rest of the array as remaining and len as 1.

5. If the current element is larger than prev, call helper recursively with the rest of the array as remaining and len incremented by 1.

6. If the current element is not larger than prev, call helper recursively with the rest of the array as remaining and len reset to 1.

7. Call helper with the first element of the array as prev, 1 as len, and the rest of the array as remaining.

Here's the implementation:

def lis(arr: Array[Int]): Int = {
  def helper(prev: Option[Int], len: Int, remaining: Array[Int]): Int = {
    if (remaining.isEmpty) len
    else if (prev.isEmpty) helper(Some(remaining.head), 1, remaining.tail)
    else if (remaining.head > prev.get) helper(Some(remaining.head), len + 1, remaining.tail)
    else helper(Some(remaining.head), 1, remaining.tail)
  }
  helper(None, 0, arr)
}

You can test the function with the following inputs:

assert(lis(Array(3, 10, 2, 1, 20)) == 2)
assert(lis(Array(3, 4, 5, 10)) == 4)
assert(lis(Array(10, 9, 8)) == 1)
assert(lis(Array(1, 2, 2)) == 2)