I recently got a subscription to Leetcode.com. I found this challenge particularly challenging:

## Challenge

Given an array nums and a target value k, find the maximum length of a subarray that sums to k. If there isn’t one, return 0 instead.

Note: The sum of the entire nums array is guaranteed to fit within the 32-bit signed integer range.

### Example 1:

```
Input: nums = [1, -1, 5, -2, 3], k = 3
Output: 4
```

**Explanation:** The subarray [1, -1, 5, -2] sums to 3 and is the longest.

### Example 2:

```
Input: nums = [-2, -1, 2, 1], k = 1
Output: 2
```

**Explanation:** The subarray [-1, 2] sums to 1 and is the longest.

### Solution:

When solving this challenge I made several mistakes. The challenge is asking us to determine the maximum sub-array length. Not the maximum sub-sequence length. A sub-array is contigous. This is a key note to solving the challenge.

#### First Attempt

In my first attempt I used a brute force algorithm. Where I determined every possible sub-array storing only the ones where the sum was equal to the given amount.

This strategy proved to be very ineffecient. As it requires several iterations to determine the output.

- First iteration determines every possible sub-array
- Second iteration for every sub-array
- Third iteration for the array of sub-arrays to determine the one with the longest length

```
def max_sub_array_len(nums, k)
sub_arrays = []
nums.each_with_index do |num, index|
slice_length = 0
while slice_length <= nums.length
sub_array = nums.slice(index, slice_length)
sum = sub_array.inject(:+)
if sum == k
sub_arrays << sub_array
end
slice_length += 1
end
end
sub_arrays.map(&:length).max || 0
end
```

#### Second Attempt

This soluion is far more efficient since we are iterating through the elements only once.

```
def max_sub_array_len(nums, k)
sum = 0
max_length = 0
history = {0 => -1}
nums.each_with_index do |num, index|
sum += num
history[sum] ||= index
if history[sum - k]
max_length = [max_length, index - history[sum - k]].max
end
end
max_length
end
```

With this solution we iterate through `nums`

and for every element we store the
current sum and current index.

Let’s walk through this solution given the following inputs.

```
nums = [1, 1, 5, -2, 3]
k = 3
```

As we iterate through the `nums`

the `sum`

and `index`

are as follows.

```
1 2 7 5 8 # sums
1, 1, 5, -2, 3 # nums
0 1 2 3 4 # index
```

We are trying to find the longest `sub_array`

with a sum of 3. Given the `nums`

input we are given there is only one `sub_array`

with the sum of 3.

```
[5, -2]
```

When iterating over the nums it is at index `3`

when iterating over `-2`

we will
determine the only correct `sub_array`

.

**Can you see why?**

At index 3 we know the following:

```
sum = 5
k = 3
```

We need to know if at any point a recorded sum is equal to the difference of sum and k (3). Let’s look at our table again. Ah, okay we can see that at index 1 the sum was 2.

```
1 2 7 5 8 # sums
1, 1, 5, -2, 3 # nums
0 1 2 3 4 # index
```

So we know our `sub_array`

must contain all elements to the left of our current
element stopping before index 1.

The correct `sub_array`

is then `[5, -2]`

with a sum equal to the `k`

input of 3.
And the correct `max_length`

determined is 2.