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()

• Kaz: Hi @stephens, I've rolledback your edit. So as to not invalidate answers, the code in the question must remain in its' original form. Please see What you can do once you've received answers. If you want to have your revised code reviewed, please post a follow-up question following the instructions in that post.
• stephens: No problem at all, apologies I should have read the rules more closely.

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

• stephens: Great ideas, thank you for taking a look. I took you function advice and implemented the following. It is much, much nicer than what I originally wrote. I have edited my original.
• SuperBiasedMan: @stephens Glad to help! As Zak explained updating the original post isn't how Code Review works, but give it time. You might get new reviews, and then when you have a full new version you could post another question and I/others can review that version.
• stephens: Thanks for the advice @SuperBiasedMan I'll be sure to do that in the future.