Find maximum number in a nested array using recursion

Question

Here is my code:

# Credit: https://www.linkedin.com/pulse/ask-recursion-during-coding-interviews-identify-good-talent-veteanu/
#
# Problem:
# Find the maximum number in a jagged array. Each element of the array can be a number or an array of
# other numbers on indefinite number of levels. For example, given an array = [1, [3, 9], 5],
# the maximum number is 9.

def max_number(array):
    if len(array) == 1 and not isinstance(array[0], list):
        return array[0]

    _array = isinstance(array[0], list) or array

    point = len(_array) // 2
    m1 = max_number(_array[:point])
    m2 = max_number(_array[point:])

    if m1 >= m2:
        print(f"m1 = {m1} larger > m2 {m2}")
        return m1
    else:
        print(f"m2 = {m2} larger > m1 {m1}")
        return m2

assert max_number([1,2,3]) == 3
assert max_number([3,2,1]) == 3
assert max_number([2,3,1]) == 3
assert max_number([1, [3, 9], 8]) == 9
assert (max_number(
     [2, 4, 10, [12, 4, [100, 99], 4], [3, 2, 99], 0]) == 100)

This is fine. The minor issue I have with is the additional isinstance check.

Originally when I worked on the solution on paper, I had forgotten about slicing a Python array [x, [w, z] ] would produce [x], and [ [w, z] ] as opposed to [w, z] for the second recursive call.

The original code looks similar, but like this:

# The original code did not verify whether the "array" argument IS a list.
# It would be this simple:

def max_number(array):
    if len(array) == 1:
        return array[0]

    point = len(array) // 2
    m1 = max_number(array[:point])
    m2 = max_number(array[point:])

    if m1 >= m2:
        print(f"m1 = {m1} larger > m2 {m2}")
        return m1
    else:
        print(f"m2 = {m2} larger > m1 {m1}")
        return m2

Could I do any better than this? Anyway without the isinstance check but still elegant?

Answer 1

Your solution is much too complicated. There is no point (pardon my pun) in splitting the array in the middle.

If you just want to demonstrate your knowledge of recursion, then apply recursion to nested lists. You can then use the max() built-in function with a generator expression.

Instead of long comments and assert statements, write docstrings with doctests.

# Credit: https://www.linkedin.com/pulse/ask-recursion-during-coding-interviews-identify-good-talent-veteanu/
def max_number(array):
    """
    Find the maximum number in a jagged array. Each element of the
    array can be a number or an array of other numbers on indefinite
    number of levels.

    >>> max_number([1, [3, 9], 5])
    9
    >>> max_number([2, 4, 10, [12, 4, [100, 99], 4], [3, 2, 99], 0])
    100
    >>> max_number([-5])
    -5
    """
    return max(
        max_number(e) if isinstance(e, list) else e
        for e in array
    )