1 | initial version |
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:
Define a function called lis
that takes an array arr
as input and returns the length of the longest increasing subarray in arr
.
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
If remaining
is empty, return len
.
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.
If the current element is larger than prev
, call helper
recursively with the rest of the array as remaining
and len
incremented by 1.
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.
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)