max_rectangle_under_budget.py

def maximum_under_budget_1d(array, budget):
    st, max_sum, max_len = 0, 0, 0
    #print(array)
    for ed in range(len(array)):
        max_sum += array[ed]
        while max_sum > budget and st <= ed:
                max_sum -= array[st]
                st += 1
        max_len = max(max_len, ed - st + 1)
    return max_len


def maximum_under_budget_2d(matrix, budget):
    M,N = len(matrix), len(matrix[0])
    max_area = 0
    
    for i in range(M):
        array1d = [0 for _ in range(N)]
        for j in range(i,M):
            array1d = [array1d[k] + matrix[j][k] for k in range(N)]
            width = maximum_under_budget_1d(array1d, budget)
            height = j - i + 1
            max_area = max(max_area, height * width)
    return max_area
        

print(maximum_under_budget_2d([[6,6,2,5],[3,5,9,7],[2,2,2,3],[1,4,3,3]], 20))