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