notatallredmart.py

import copy
import sys
def greater_path(path1,path2):
  (path_list1,elevation1,last_heightl1) = path1
  (path_list2,elevation2,last_heightl2) = path2
  len1 = len(path_list1)
  len2 = len(path_list2)
  if len1 != len2:
    return len1 > len2
  return elevation1 > elevation2
 
def get_neighbours(arrsize,point):
  rcount,ccount = arrsize
  i,j = point
  deltas = [(-1,0),(0,-1),(1,0),(0,1)]
  points = ((x+i,y+j) for (x,y) in deltas)
  points = filter(lambda (x,y): (x>=0 and x<rcount) and (y >= 0 and y<ccount),points)
  return points
 
def is_higher(arr,point1,point2):
  i,j = point1
  ii,jj = point2
  return arr[i][j] < arr[ii][jj]
 
def split_neighbours(neighbours,arr,i,j):
  higher,lower = [],[]
  higher = filter(lambda (x,y): is_higher(arr,(i,j),(x,y)),neighbours)
  lower = filter(lambda (x,y): not is_higher(arr,(i,j),(x,y)),neighbours)
  return higher,lower
 
def get_max(path1,path2):
  return path1 if greater_path(path1,path2) else path2 
 
def update_paths(paths,arr,i,j):
  elevation = arr[i][j]
  arrsize = len(arr),len(arr[0])
  neighbours = get_neighbours(arrsize,(i,j))
  higher_neighbours,lower_neighbours = split_neighbours(neighbours,arr,i,j)
  lower_paths = [paths[neighbour] for neighbour in lower_neighbours if  paths.get(neighbour) is not None]
  if lower_paths == []:
    paths[(i,j)]=([(i,j)],0,elevation)
  else:
    path,elevation_sofar,last_elevation = reduce(get_max,lower_paths)
    path = copy.deepcopy(path)
    path.append((i,j))
    paths[(i,j)] = (path,elevation_sofar+elevation-last_elevation,elevation)
  for ii,jj in  higher_neighbours:
    update_paths(paths,arr,ii,jj)
 
def solve(arr,paths):
  for i,row in enumerate(arr):
    for j,point in enumerate(row):
      update_paths(paths,arr,i,j)

def get_array_from_file(f):
  a = []
  row,col = map(int,f.readline().split())
  i = 0 ; 
  while i < row:
    a.append(map(int,f.readline().split()))
    i=i+1
  return a 

if __name__ == '__main__':
  paths = {}
  f = None
  if len(sys.argv) == 1:
    f = sys.stdin
  else:
    f = open(sys.argv[1],"r")
  arr = get_array_from_file(f)
  solve(arr,paths)
  print reduce(get_max,paths.values())