# 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:
#
# Input: matrix = [[1,0,1],[0,-2,3]], k = 2
# Output: 2
# Explanation: Because the sum of rectangle [[0, 1], [-2, 3]] is 2,
#              and 2 is the max number no larger than k (k = 2).
# Note:
#
# The rectangle inside the matrix must have an area > 0.
# What if the number of rows is much larger than the number of columns?
import bisect


class Solution(object):
    def maxSumSubmatrix(self, matrix, k):
        """
        :type matrix: List[List[int]]
        :type k: int
        :rtype: int
        """
        m, n, res = len(matrix), len(matrix[0]), float('-inf')

        for i in xrange(n):
            dp = [0] * m
            for j in xrange(i, n):
                for l in xrange(m):
                    dp[l] += matrix[l][j]

                curSum, S = 0, {0}

                for a in dp:
                    curSum += a
                    arr = sorted([v for v in S])
                    idx = bisect.bisect_left(arr, curSum - k)
                    if idx < len(arr):
                        res = max(res, curSum - arr[idx])
                    S.add(curSum)

        return res

    def maxSumSubmatrix3(self, matrix, k):
        """
        :type matrix: List[List[int]]
        :type k: int
        :rtype: int
        """
        m = len(matrix)
        n = len(matrix[0]) if m else 0

        M = max(m, n)
        N = min(m, n)
        ans = None
        for x in range(N):
            sums = [0] * M
            for y in range(x, N):
                slist, num = [], 0
                for z in range(M):
                    sums[z] += matrix[z][y] if m > n else matrix[y][z]
                    num += sums[z]
                    if num <= k: ans = max(ans, num)
                    i = bisect.bisect_left(slist, num - k)
                    if i != len(slist): ans = max(ans, num - slist[i])
                    bisect.insort(slist, num)
        return ans or 0


def maxSumSubmatrix2(self, matrix, k):
    def maxSumSublist(vals):
        maxSum = float('-inf')
        prefixSum = 0
        prefixSums = [float('inf')]
        for val in vals:
            bisect.insort(prefixSums, prefixSum)
            prefixSum += val
            i = bisect.bisect_left(prefixSums, prefixSum - k)
            maxSum = max(maxSum, prefixSum - prefixSums[i])
        return maxSum

    maxSum = float('-inf')
    columns = zip(*matrix)
    for left in range(len(columns)):
        rowSums = [0] * len(matrix)
        for column in columns[left:]:
            rowSums = map(int.__add__, rowSums, column)
            maxSum = max(maxSum, maxSumSublist(rowSums))
    return maxSum

if __name__ == '__main__':
    print Solution().maxSumSubmatrix([[2, 2, -1]], 0)
    print Solution().maxSumSubmatrix([[1, 0, 1], [0, -2, 3]], 2)
