package main
import (
"fmt"
)
// Function to find the maximum length of a subarray with sum equal to K
func maxLengthSubarrayEqualsToK(arr []int, K int) int {
// To store cumulative sum and its earliest index
sumIndexMap := make(map[int]int)
maxLength := 0
cumulativeSum := 0
for i := 0; i < len(arr); i++ {
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 idx, exists := sumIndexMap[cumulativeSum-K]; exists {
if i - idx > maxLength {
maxLength = i - idx
}
}
// Store the cumulative sum in the map if not already present
if _, exists := sumIndexMap[cumulativeSum]; !exists {
sumIndexMap[cumulativeSum] = i
}
}
return maxLength
}
func main() {
arr := []int{1, -1, 5, -2, -3, 2, 3, 3}
K := 3
// 1, -1, 5, -2 = 3 (length 4)
// 5, -2 = 3 (length 2)
// -2, -3, 2, 3, 3 = 3 (length 5)
fmt.Println(maxLengthSubarrayEqualsToK(arr, K))
}
/*
run:
5
*/
