# !/usr/bin/env python
# coding: utf-8

'''
Description:
    Given a non-empty 2D matrix matrix and an integer k,
    find the max sum of a rectangle in the matrix such that its sum is no larger than k.

    Example:
        Given matrix = [
          [1,  0, 1],
          [0, -2, 3]
        ]
        k = 2
    The answer is 2. Because the sum of rectangle [[0, 1], [-2, 3]] is 2 and 2 is the max number no larger than k (k = 2).

Note:
    1. The rectangle inside the matrix must have an area > 0.
    2. What if the number of rows is much larger than the number of columns?

Tags: Binary Search, Dynamic Programming, Queue
'''
