I am trying to write a recursive function in order to find the max integer in a list of list. I know how to write a func for list of ints. Can anyone give me some tips for this?I I am thinking doing it with no Max function. ex. a = [1, [2,3], 4, [[2], 1]] find_max(a) ->4
1
-
However It's not a good question for SO , but please specify some samples for better undestanding into your problemᴀʀᴍᴀɴ– ᴀʀᴍᴀɴ2016-02-21 18:41:19 +00:00Commented Feb 21, 2016 at 18:41
Add a comment
|
2 Answers
I decided to tackle this with pure recursion, no loops. The following seems to do the trick for me:
def find_max(a_list):
l = len(a_list)
if l > 1: # if there are multiple elements...
l /= 2 # find the midpoint
m1 = find_max(a_list[:l]) # find the max in the first half
m2 = find_max(a_list[l:]) # find the max in the second half
if m1 > m2: # pick between them
return m1
else:
return m2
elif l < 1: # deal with empty lists
return None
else: # we're down to one element...
if isinstance(a_list[0], list): # ...but it may be a list
return find_max(a_list[0]) # if so, find its max
else:
return a_list[0] # otherwise, a single element is trivially the max of its subset
Note that by splitting the subproblems in half rather than reducing by 1, this implementation should be robust against stack overflows even with large lists.
Now revised to deal with empty lists.
You can iterate through your list and call the MAX() function if data type is a list:
l = [[54,65,464,656,5],[568,49,7,8,4,3,3515],[312,64,598,46]]
def MAX(l):
mx = None
for item in l:
if isinstance(item, list):
tmp = MAX(item)
else:
tmp = item
if mx < tmp:
mx = tmp
return mx
5 Comments
Kenly
@bxlt I am glad to help you.Feel free to accept one answer (for the community).
pjs
This will return -1 if all the numbers in the list are negative values below -1.
Kenly
@pjs His list contain only positive numbers.Thank you for this observation.
pjs
@WoLy His example list contained only positive numbers. His description said "ints", not positive ints. A valid algorithm should deal with all cases. Yours can be fixed, but isn't general as-written.
Kenly
@pjs Thank you for this reply.Please if you have time help us to fix it.