Find the longest subset with sum less than K

almost 5 years ago.

In the course of finding an internship I applied to bunch of the top tech companies. Some refused my application, other ignore it. One gave me a programming challenge (I can't say the name unfortunately) in which I got a couple of interesting problems to solve.

One of the problems consist of finding the longest subset with a sum less than a given integer.

The input data are:
* 'K' the max sum
* 'a' an array of integers

my first approach as always is "don't reinvent the wheel" and Google it to find the optimal algorithm. However this is a challenge in which my programming skills are tested so I grabbed pen and papers and start with the most obvious way.

```- start at the "start" position
- start summing up until we go over K
- save the length
- increment the "start" position
- and repeat
```

In python

```def length_max_subarray(a, K):
length = 0
start = 0
finish = 0
while(start<len(a)):
finish = 0
s = sum(a[start:start+finish])
while(start+finish<=len(a) and s<=K ):
if finish > length:
length = finish
finish+=1
s = sum(a[start:start+finish])
start+=1
return length
```

As you can see this is in the order of O( N2 ) of course we can save some steps for example we don't need to reset the finish to zero we can directly set it up to length

```....
while(start<len(a)):
finish = length
s = sum(a[start:start+finish])
while(start+finish<=len(a) and s<=K ):
....
```

However this doesn't give us a performance boost we need to find a solution to lower the order of magnitude

# Optimization

I got the idea of using a head and tail and keep the current sum

```head = tail = 0

-while the tail is less than the length of the array
-increment the tail and update the sum
-if the sum go over the max sum increment the head until the sum is less than K
- while incrementing the tail check if we have a new max_length

```

The code:

```def length_max_subarray(array, K):
length = 0
current_sum = 0
while(tail<len(array)):
if current_sum + array[tail]<=K:
current_sum += array[tail]
tail+=1