The problem consist of finding the longest contiguous subarray with a sum less than a given integer
The input data are:
K- the max sum
array- 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?