The problem consist of finding the longest contiguous subarray with a sum less than a given integer K
.
The input data are:
K
- the max sumarray
- an array of integers
The algorithm I developed:
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 K, increment the head until the sum is less than K
- while incrementing the tail check if we have a new max_length
The Python code:
def length_max_subarray(array, K):
head, tail = 0, 0
length = 0
current_sum = 0
while(tail<len(array)):
if current_sum + array[tail]<=K:
current_sum += array[tail]
tail+=1
if tail-head > length:
length = tail-head
else:
current_sum -= array[head]
head+=1
return length
My assumption is "this code is \$O(N)\$" because:
The worst case is when all elements are larger than K
. In that case the while loop will increment the head and the tail successively so the number of iterations is \$2*N\$.
Is it true? If not, what's the complexity of this code?
array
here is a pythonlist
? \$\endgroup\$less than
, then it should be< K
instead of<= K
, right? \$\endgroup\$