matrix-land.py

import sys
from array import array

def matrixLand(grid):
    width = len(grid[0])
    prevline = array('l',[0]) * width

    for line in grid:
        going_left = array('l',[0]) * width
        going_right = array('l',[0]) * width

        top, notop = -2000000000, 0
        for i in range(width):
            notop = max(0,notop)
            going_right[i] += notop
            notop += line[i]
            top = max(top+line[i], prevline[i]+notop)
            going_left[i] += top

        top, notop = -2000000000, 0
        for i in range(width-1,-1,-1):
            notop = max(0,notop)
            going_left[i] += notop
            notop += line[i]
            top = max(top+line[i], prevline[i]+notop)
            going_right[i] += top

        for i in range(width):
            prevline[i] = max(going_left[i], going_right[i])

    return max(prevline)


n, m = [int(x) for x in input().split()]

if m == 1:
    print(sum(int(x) for x in sys.stdin))
else:
    grid = []
    for _ in range(n):
        grid.append(array('l',(int(x) for x in sys.stdin.readline().split(' '))))
    result = matrixLand(grid)
    print(result)