Time Limit Exceeded Your program took more time than expected. Expected Time Limit: 2.49sec
1st Code:
subarr = []
N = n 1 - k
for i in range(N):
S = arr[i:i k]
subarr.append(max(S))
return subarr
2nd Code:
l=[max(arr[:k])]
for i in range(k,n):
if l[-1]==arr[i-k]:
l.append(max(arr[i-k 1:i 1]))
elif l[-1]>arr[i]:
l.append(l[-1])
else:
l.append(arr[i])
return l
CodePudding user response:
The second algorithm is smarter and does not call max
on a newly created slice in every iteration. Creating a slice is a relative costly operation, so by avoiding it in some iterations, it will gain time.
You could express that second algorithm's loop in words like this:
If the previous subrange starts with the maximum value I identified for it, then that maximum will no longer be part of the current subrange, so I'll have to determine the new maximum by finding it using
max
.Otherwise, that maximum will still be in the current subrange. If the current value that is going to be the newest member of the current range is less than that maximum, then the maximum will remain the same as I had for the previous range, so just copy it.
If however, the current value that is going to be part of the current range, is greater than the maximum I had, then forget about that previous maximum, and let this be the maximum for the current range.
The logic of the last two steps makes it possible to know the maximum of the current range without performing a slice max operation.