import scala.collection.mutable
object MaxLengthSubarray {
def maxLengthSubarrayEqualsToK(arr: Array[Int], K: Int): Int = {
val map = mutable.Map[Int, Int]() // To store cumulative sum and its index
var maxLength = 0
var cumulativeSum = 0
for (i <- arr.indices) {
cumulativeSum += arr(i)
// If the cumulative sum equals K, update maxLength
if (cumulativeSum == K) {
maxLength = i + 1
}
// If (cumulativeSum - K) exists in the map, update maxLength
if (map.contains(cumulativeSum - K)) {
maxLength = math.max(maxLength, i - map(cumulativeSum - K))
}
// Store the cumulative sum in the map if not already present
if (!map.contains(cumulativeSum)) {
map(cumulativeSum) = i
}
}
maxLength
}
def main(args: Array[String]): Unit = {
val arr = Array(1, -1, 5, -2, -3, 2, 3, 3)
val K = 3
// 1, -1, 5, -2 = 3 (length 4)
// 5, -2 = 3 (length 2)
// -2, -3, 2, 3, 3 = 3 (length 5)
println(maxLengthSubarrayEqualsToK(arr, K))
}
}
/*
run:
5
*/
