Find the largest continuous descending sum in a 2d matrix

Question

Given a 2d array, the problem is to find the largest sum, where each subsequent is >= the previous digit but < all of the 'neighbour' digits. You can only move up, down, left and right.

My solution will run in \$O(N*M)\$ time with \$O(N*M)\$ space (please correct me if I'm wrong).

The solution is as follows: Start at an arbitrary point and look for the closest largest neighbor (as described above). Once found, append it to the path and mark as visited. Continue these steps until you have no where else to visit.

Code is below, with the the answer being [10, 9, 6, 4, 2]. Thank you

nums = [
  [10,8,4],
  [9,6,8],
  [2,4,3]
]

def get_largest_neighbour(i, j, previous, visited):
    max_location = -1, -1
    max_neighbour = -1

    # look up
    if i-1 >= 0 and nums[i-1][j] < previous and visited[i-1][j] == False:
        max_neighbour = nums[i-1][j]
        max_location = i-1, j

    # look down
    if i+1 < 3:
        if nums[i+1][j] > max_neighbour and nums[i+1][j] < previous and visited[i+1][j] == False:
            max_neighbour = nums[i+1][j]
            max_location = i+1, j 

    # look left
    if j-1 >= 0:
        if nums[i][j-1] > max_neighbour and nums[i][j-1] < previous and visited[i][j-1] == False:
            max_neighbour = nums[i][j-1]
            max_location = i, j-1

    # look right
    if j+1 < 3:
        if nums[i][j+1] > max_neighbour and nums[i][j+1] < previous and visited[i][j+1] == False:
            max_neighbour = nums[i][j+1]
            max_location = i, j+1

    return max_location

def max_sum(i, j, path, visited):
    if i >= 3 or i < 0 or j >= 3 or j < 0:
        return

    if visited[i][j] == True:
        return

    # mark as visited and append to path
    visited[i][j] = True
    path.append(nums[i][j])

    # find the next largest path to search
    next_step_i, next_step_j = get_largest_neighbour(i, j, path[-1], visited)

    # there is no where to go, so stop iterating and backtrack
    if next_step_i == -1:
        return

    max_sum(next_step_i, next_step_j, path, visited)

    return path

def largest_continious_sum():
    if len(nums) <= 1:
        return 0

    visited = [[False for x in range(3)] for j in range(3)]
    path = []

    print max_sum(0, 0, path, visited)

largest_continious_sum()

Answer 1

get_largest_neighbour is a big confusing function. Let's try strip it down to avoid rewriting code.

First I would create a loop to run on each of the four directions. To loop, you want to make a list of the four positions and loop over each. To do that, you can just build a simple tuple of co-ordinates were you add and subtract one from i and j in turn:

coordinates = ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1))
for x, y in coordinates:

Now you need to fold all your tests to make sure they're in the right range into one, which is simple enough and more readable in my opinion:

    if not 0 <= x < len(nums) or not 0 <= y < len(nums[0]):
        continue

To break it down a bit, the range we want is for x and y to be 0 or greater, and less than the length of the lists. Rather than hardcode 3, it's better to use len of the matrix. If you're concerned about performance for larger matrices, you could precalculate these values. If either of these values isn't valid for their range, then continue is called, with will skip onto the next co-ordinate and not run the rest of the loop.

Now all you need is your actual test and re-setting the max values. For convenience, I'd grab the value of nums[x][y] before the test:

    num = nums[x][y]
    if previous > num > max_neighbour and not visited[x][y]:
        max_neighbour = num
        max_location = x, y

You notice I also changed your if test, to make a single range test and to replace == False with not. Both make it easier to see what you're actually testing.

Now your code is much simpler, easier to adjust and easier to read:

def get_largest_neighbour(i, j, previous, visited):
    max_location = -1, -1
    max_neighbour = -1
    coordinates = ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1))

    for x, y in coordinates:
        if not 0 <= x < len(nums) or not 0 <= y < len(nums[0]):
            continue

        num = nums[x][y]
        if previous > num > max_neighbour and not visited[x][y]:
            max_neighbour = num
            max_location = x, y

    return max_location