codeingame/max_rect.py

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