The idea comes from the C++ or Java solution posted on discuss, I just rewrite the idea with python.

- using two pointers to scan the column, Space is O(col)
`left`

and`right`

both start from the 0, and move`right`

first when it reaches the end then move`left`

- record the sum of the value and find the max sum less than k
- the following code can also be used to solve
`Max Sum of Sub-Matrix`

, only need to replace the`maxSubArraylessK`

with`Kadane's algorithm`

```
def maxSubArraylessK(self,nums,k):
"""
we need to find the sum[right]-sum[left]<=k
since the bitsect return the index of the sorted value
we can't directly pop the nums[idx]
we should use insort from the bisect
"""
# python set() doesn't support indexing, using list instead
# similar as the c++ or java set()
cumset=[]
cumset.append(0)
maxsum=-1<<32
cursum=0
for i in xrange(len(nums)):
cursum+=nums[i]
# find the lower bound of the index
idx=bisect.bisect_left(cumset,cursum-k)
# find max in sum[right]-sum[left]<=k
if 0<=idx<len(cumset):
maxsum=max(maxsum,cursum-cumset[idx])
# using insort instead of append since bisect_left reason
bisect.insort(cumset,cursum)
return maxsum
def maxSumSubmatrix(self, matrix, k):
"""
:type matrix: List[List[int]]
:type k: int
:rtype: int
"""
"""
The python solution hasn't a good time performance,
since lack some of the datatype to do
I am trying to imitate the way solved in c++ or Java
Ther related quesiton might be:
1. #53. Maximum Subarray
2. Maximum Subarray sum less or equal than K
3. maximun sum of rectangle
"""
if not matrix or not matrix[0]:
return 0
row,col=len(matrix),len(matrix[0])
res=-(1<<32)
# using two pointer to record the scan position
for left in xrange(col):
# reset mem to store the row data
cursums=[0 for _ in xrange(row)]
# since the rectange has area>0
right=left
while right<col:
# count one row
for i in xrange(row):
cursums[i]+=matrix[i][right]
# find the max in this row
curarrmax=self.maxSubArraylessK(cursums,k)
res=max(res,curarrmax)
right+=1
return res
```