''' > https://www.codingame.com/ide/1850615487c96262f26bd2d508cb46b18cc23557 @author: olivier.massot, 2019 ''' import sys # w, h = [int(i) for i in input().split()] # rows = [[int(x) for x in input().split()] for _ in range(h)] w,h=2,2 rows = [[99,0], [0,-1], [0,2], ] def max_subarray_1d(row): max_so_far, max_ending_here = 0, row[0] for v in row[1:]: max_ending_here = max(v, max_ending_here + v) max_so_far = max(max_so_far, max_ending_here) return max_so_far def max_subarray_2d(rows): w, h = len(rows[0]), len(rows) # Modify the array's elements to now hold the sum # of all the numbers that are above that element in its column summed=[[*row] for row in rows] for y in range(1, h): for x in range(w): summed[y][x] += summed[y-1][x] ans = 0 for y0 in range(h-1): for y1 in range(y0+1, h): sums = [summed[y1][x] - summed[y0][x] for x in range(w)] ans = max(ans, max_subarray_1d(sums)) for y in range(h): ans = max(ans, max_subarray_1d(summed[y])) ans = max(ans, max_subarray_1d(rows[y])) ans=max(ans, sum((sum(row) for row in rows))) return ans if all(v >= 0 for row in rows for v in row): print("special: all positives", file=sys.stderr) print(sum((sum(row) for row in rows))) elif all(v <= 0 for row in rows for v in row): print("special: all negatives", file=sys.stderr) print(max(max(row) for row in rows)) elif len(rows[0]) == 1: print("special: one column", file=sys.stderr) maxsub = max_subarray_1d([row[0] for row in rows]) print(maxsub) elif len(rows) == 1: print("special: one row", file=sys.stderr) maxsub = max_subarray_1d(rows[0]) print(maxsub) else: maxsub = max_subarray_2d(rows) print(maxsub)