Given a 2D matrix M of dimensions RxC. Find the maximum sum submatrix in it.
Example 1:
Input:
R=4
C=5
M=[[1,2,-1,-4,-20],
[-8,-3,4,2,1],
[3,8,10,1,3],
[-4,-1,1,7,-6]]
Output:
29
Explanation:
The matrix is as follows and the
blue rectangle denotes the maximum sum
rectangle.
Example 2:
Input:
R=2
C=2
M=[[-1,-2],[-3,-4]]
Output:
-1
Explanation:
Taking only the first cell is the 
optimal choice.
Your Task:
You don't need to read input or print anything. Your task is to complete the function maximumSumRectangle() which takes the number R, C, and the 2D matrix M as input parameters and returns the maximum sum submatrix.
Expected Time Complexity:O(R*R*C)
Expected Auxillary Space:O(R*C)
 
Constraints:
1<=R,C<=500
-1000<=M[i][j]<=1000

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Matrices

Dynamic programming

Data structures

Range queries

Starter code: #User function Template for python3





class Solution:

    def maximumSumRectangle(self,R,C,M):

        #code here

Solutions:
class Solution:

	def maximumSumRectangle(self, R, C, M):
		pre = [[0] * (C + 1) for i in range(0, R)]
		ans = -1000000000000000
		for i in range(0, R):
			for j in range(0, C):
				pre[i][j + 1] += pre[i][j] + M[i][j]
				ans = max(ans, M[i][j])
		for i in range(0, C):
			for j in range(i, C):
				(sy, ey) = (i, j + 1)
				ca = -1000000000000000
				mtt = -1000000000000000
				for k in range(0, R):
					cv = pre[k][ey] - pre[k][sy]
					mtt = max(cv, cv + mtt)
					ca = max(ca, mtt)
				ans = max(ans, ca)
		return ans


class Solution:

	def maximumSumRectangle(self, R, C, M):
		maxVal = -float('inf')
		for cStart in range(C):
			temp = [0 for _ in range(R)]
			for cEnd in range(cStart, C):
				for r in range(R):
					temp[r] += M[r][cEnd]
				currSum = 0
				for elem in temp:
					currSum += elem
					maxVal = max(maxVal, currSum)
					if currSum < 0:
						currSum = 0
		return maxVal


class Solution:

	def kadens(self, arr):
		mx = -999
		su = 0
		for i in arr:
			su += i
			mx = max(su, mx)
			if su < 0:
				su = 0
		return mx

	def maximumSumRectangle(self, R, C, M):
		mxans = -99999
		for i in range(C):
			arr = [0] * R
			for j in range(i, C):
				for k in range(R):
					arr[k] += M[k][j]
				currsu = self.kadens(arr)
				mxans = max(currsu, mxans)
		return mxans


class Solution:

	def kadane(self, ar):
		mx = float('-inf')
		c = 0
		for i in ar:
			c += i
			mx = max(c, mx)
			if c < 0:
				c = 0
		return mx

	def maximumSumRectangle(self, r, c, arr):
		res = float('-inf')
		for i in range(r):
			x = [0] * c
			for j in range(i, r):
				for k in range(c):
					x[k] += arr[j][k]
				res = max(res, self.kadane(x))
		return res


import sys

class Solution:

	def kadane(self, arr, n):
		maxa = -(sys.maxsize - 1)
		temp = 0
		for el in arr:
			temp = temp + el
			if temp > maxa:
				maxa = temp
			if temp < 0:
				temp = 0
		return maxa

	def dp_sol(self, R, C, M):
		temp = [0] * R
		Cc = 0
		maxi = -(sys.maxsize - 1)
		for i in range(C):
			for j in range(i, C):
				for k in range(R):
					temp[k] = temp[k] + M[k][j]
				maxi = max(maxi, self.kadane(temp, R))
			temp = [0] * R
		return maxi

	def maximumSumRectangle(self, R, C, M):
		return self.dp_sol(R, C, M)


class Solution:

	def maximumSumRectangle(self, R, C, M):
		for r in M:
			for i in range(1, C):
				r[i] += r[i - 1]
		ans = float('-inf')
		for l in range(C):
			for r in range(l, C):
				running = 0
				for i in range(R):
					v = M[i][r]
					if l > 0:
						v -= M[i][l - 1]
					running += v
					ans = max(ans, running)
					if running < 0:
						running = 0
		return ans


class Solution:

	def rowWiseKedan(self, mat):
		summ = 0
		maxSum = float('-inf')
		for i in range(len(mat)):
			summ += mat[i]
			maxSum = max(maxSum, summ)
			if summ < 0:
				summ = 0
		return maxSum

	def maximumSumRectangle(self, R, C, A):
		n = len(A)
		m = len(A[0])
		maxSum = float('-inf')
		for i in range(m):
			temp = [0] * n
			for j in range(i, m):
				for k in range(n):
					temp[k] += A[k][j]
				maxSum = max(maxSum, self.rowWiseKedan(temp))
		return maxSum


class Solution:

	def kadane(self, ans):
		cur_sum = 0
		best_sum = float('-inf')
		for val in ans:
			if cur_sum <= 0:
				cur_sum = val
			else:
				cur_sum += val
			best_sum = max(best_sum, cur_sum)
		return best_sum

	def maximumSumRectangle(self, R, C, M):
		maxVal = float('-inf')
		for i in range(R):
			ans = [0] * C
			for j in range(i, R):
				for elem in range(C):
					ans[elem] += M[j][elem]
				maxVal = max(maxVal, self.kadane(ans))
		return maxVal


class Solution:

	def maximumSumRectangle(self, R, C, M):
		ans = -99999
		for i in range(C):
			arr = [0] * R
			for j in range(i, C):
				for k in range(R):
					arr[k] = arr[k] + M[k][j]
				curr_sum = self.submatrix(arr)
				ans = max(curr_sum, ans)
		return ans

	def submatrix(self, arr):
		mx = -999
		sum = 0
		for i in arr:
			sum = sum + i
			mx = max(sum, mx)
			if sum < 0:
				sum = 0
		return mx


class Solution:

	def kadane(self, arr):
		n = len(arr)
		(cur_sm, mx_sm) = (0, max(arr))
		for i in range(n):
			cur_sm += arr[i]
			mx_sm = max(mx_sm, cur_sm)
			if cur_sm <= 0:
				cur_sm = 0
		return mx_sm

	def maximumSumRectangle(self, R, C, M):
		max_res = -float('inf')
		for i in range(C):
			arr = [0] * R
			for j in range(i, C):
				for k in range(R):
					arr[k] += M[k][j]
				cr_val = self.kadane(arr)
				max_res = max(max_res, cr_val)
		return max_res


class Solution:

	def kadane(self, arr):
		n = len(arr)
		(cur_sm, mx_sm) = (0, max(arr))
		for i in range(n):
			cur_sm += arr[i]
			mx_sm = max(mx_sm, cur_sm)
			if cur_sm <= 0:
				cur_sm = 0
		return mx_sm

	def maximumSumRectangle(self, R, C, M):
		mxans = -99999
		for i in range(C):
			arr = [0] * R
			for j in range(i, C):
				for k in range(R):
					arr[k] += M[k][j]
				currsu = self.kadane(arr)
				mxans = max(currsu, mxans)
		return mxans


class Solution:

	def maximumSumRectangle(self, R, C, M):

		def kadanes(arr):
			ans = -1000000000.0
			summ = 0
			for i in arr:
				summ = summ + i
				ans = max(ans, summ)
				if summ < 0:
					summ = 0
			return ans
		maxi = -1000000000.0
		for i in range(R):
			arr = [0] * C
			for j in range(i, R):
				for k in range(C):
					arr[k] += M[j][k]
				maxi = max(maxi, kadanes(arr))
		return maxi


class Solution:

	def maximumSumRectangle(self, r, c, a):
		n = r
		m = c
		maxval = -999999999
		r1 = -1
		r2 = -1
		c11 = -1
		c12 = -1
		for c1 in range(m):
			column = []
			for c2 in range(c1, m):
				for i in range(n):
					if c1 == c2:
						column.append(a[i][c2])
					else:
						column[i] += a[i][c2]
				currsum = 0
				ind = 0
				for i in range(n):
					currsum += column[i]
					if maxval < currsum:
						maxval = max(maxval, currsum)
						r1 = ind
						c11 = c1
						r2 = i
						c12 = c2
					if currsum < 0:
						currsum = 0
						ind = i + 1
		return maxval


class Solution:

	def kadane(self, l, n):
		s = 0
		ans = l[0]
		for i in range(n):
			s += l[i]
			ans = max(ans, s)
			if s < 0:
				s = 0
		return ans

	def maximumSumRectangle(self, R, C, M):
		ans = -100000
		s = 0
		for i in range(C):
			temp = [0] * R
			for j in range(i, C):
				for k in range(R):
					temp[k] += M[k][j]
				s = self.kadane(temp, R)
				ans = max(s, ans)
		return ans


class Solution:

	def maximumSumRectangle(self, R, C, M):

		def kadane(arr):
			n = len(arr)
			a = [0 for i in range(n)]
			a[0] = arr[0]
			for i in range(1, n):
				if arr[i] < arr[i] + a[i - 1]:
					a[i] = arr[i] + a[i - 1]
				else:
					a[i] = arr[i]
			return max(a)
		ans = float('-inf')
		for i in range(R):
			l = [0] * C
			for j in range(i, R):
				for k in range(C):
					l[k] = l[k] + M[j][k]
				ans = max(ans, kadane(l.copy()))
		return ans


class Solution:

	def maximumSumRectangle(self, R, C, M):

		def kadane(a):
			max_sum = a[0]
			cur_sum = a[0]
			for i in range(1, len(a)):
				cur_sum = max(a[i], cur_sum + a[i])
				max_sum = max(max_sum, cur_sum)
			return max_sum
		gsum = float('-inf')
		for left in range(len(M[0])):
			temp = [0] * len(M)
			for right in range(left, len(M[0])):
				for i in range(len(M)):
					temp[i] += M[i][right]
				Sum = kadane(temp)
				if Sum > gsum:
					gsum = Sum
		return gsum


import math

class Solution:

	def Get_Max_Sum_Sub_Array(self, arr):
		(ans, current_sum) = (-math.inf, 0)
		for num in arr:
			current_sum += num
			ans = max(ans, current_sum)
			if current_sum < 0:
				current_sum = 0
		return ans

	def maximumSumRectangle(self, R, C, M):
		(row, col, ans, arr) = (R, C, -math.inf, M)
		for i in range(1, row):
			for j in range(col):
				arr[i][j] += arr[i - 1][j]
		for row1 in range(row):
			for row2 in range(row1, row):
				temp = []
				for j in range(col):
					temp.append(arr[row2][j] - arr[row1 - 1][j] if row1 else arr[row2][j])
				ans = max(ans, self.Get_Max_Sum_Sub_Array(temp))
		return ans


import sys

class Solution:

	def kadens(self, arr):
		cur_sum = arr[0]
		max_sum = arr[0]
		for i in range(1, len(arr)):
			cur_sum = max(arr[i], cur_sum + arr[i])
			max_sum = max(cur_sum, max_sum)
		return max_sum

	def maximumSumRectangle(self, R, C, M):
		mxans = -99999
		for i in range(C):
			arr = [0] * R
			for j in range(i, C):
				for k in range(R):
					arr[k] += M[k][j]
				currsu = self.kadens(arr)
				mxans = max(currsu, mxans)
		return mxans


class Solution:

	def maximumSumRectangle(self, R, C, M):
		maxi = -32676
		for i in range(R):
			arr = [0] * C
			for i1 in range(i, R):
				for j in range(0, C):
					arr[j] = arr[j] + M[i1][j]
				maxi = self.Kaden(i, M, arr, maxi)
		return maxi

	def Kaden(self, i, M, arr, maxi):
		summ = 0
		for i in range(0, len(arr)):
			summ = summ + arr[i]
			if summ > maxi:
				maxi = summ
			if summ <= 0:
				summ = 0
		return maxi


class Solution:

	def maximumSumRectangle(self, row, col, arr):

		def kadane(arr):
			if max(arr) < 0:
				return max(arr)
			maxsum = -1000000000.0
			curr = 0
			for i in arr:
				curr += i
				maxsum = max(maxsum, curr)
				if curr < 0:
					curr = 0
			return maxsum
		maxi = -1000000000.0
		for i in range(col):
			temp = [0] * row
			for j in range(i, col):
				for k in range(row):
					temp[k] += arr[k][j]
				Sum = kadane(temp)
				maxi = max(maxi, Sum)
		return maxi


class Solution:

	def maximumSumRectangle(self, R, C, A):

		def kadane(v):
			currSum = 0
			maxSum = -sys.maxsize - 1
			for i in range(len(v)):
				currSum = max(currSum + v[i], v[i])
				maxSum = max(maxSum, currSum)
			return maxSum
		r = len(A)
		c = len(A[0])
		prefix = [[0 for i in range(c)] for j in range(r)]
		for i in range(r):
			for j in range(c):
				if j == 0:
					prefix[i][j] = A[i][j]
				else:
					prefix[i][j] = A[i][j] + prefix[i][j - 1]
		maxSum = -sys.maxsize - 1
		for i in range(c):
			for j in range(i, c):
				v = []
				for k in range(r):
					el = 0
					if i == 0:
						el = prefix[k][j]
					else:
						el = prefix[k][j] - prefix[k][i - 1]
					v.append(el)
				maxSum = max(maxSum, kadane(v))
		return maxSum


class Solution:

	def maximumSumRectangle(self, R, C, M):
		maxSum = -9999999
		sum1 = 0
		for left in range(C):
			stored = [0] * R
			for right in range(left, C):
				for i in range(R):
					stored[i] += M[i][right]
				currSum = 0
				maxSum2 = -9999999
				for i in range(R):
					currSum += stored[i]
					if currSum > maxSum2:
						maxSum2 = currSum
					if currSum < 0:
						currSum = 0
				if maxSum2 > maxSum:
					maxSum = maxSum2
		return maxSum


class Solution:

	def maximumSumRectangle(self, R, C, M):

		def Kadane(arr):
			mfar = -float('inf')
			mend = 0
			for _ in range(len(arr)):
				mend = mend + arr[_]
				if mend > mfar:
					mfar = mend
				if mend < 0:
					mend = 0
			return mfar
		maxSum = -float('inf')
		for i in range(C):
			dp = [0] * R
			for k in range(i, C):
				for j in range(R):
					dp[j] = dp[j] + M[j][k]
				maxSum = max(Kadane(dp), maxSum)
		return maxSum


class Solution:

	def maximumSumRectangle(self, R, C, M):

		def kadaneAlgo(nums):
			cur_sum = 0
			max_sum = -99999999
			for num in nums:
				cur_sum += num
				max_sum = max(max_sum, cur_sum)
				if cur_sum < 0:
					cur_sum = 0
			return max_sum
		m = len(M)
		n = len(M[0])
		nums = [0 for _ in range(n)]
		res = -9999999999
		for i in range(m):
			for j in range(i, m):
				if i == j:
					nums = M[i]
					res = max(res, kadaneAlgo(M[i]))
				else:
					for k in range(n):
						nums[k] = nums[k] + M[j][k]
					res = max(res, kadaneAlgo(nums))
		return res


class Solution:

	def maximumSumRectangle(self, R, C, M):

		def kadane(a):
			temp = float('-inf')
			res = float('-inf')
			for i in a:
				temp = max(i, temp + i)
				res = max(res, temp)
			return res
		maxSum = float('-inf')
		for cStart in range(C):
			arr = [0 for i in range(R)]
			for cEnd in range(cStart, C):
				for row in range(R):
					arr[row] += M[row][cEnd]
				currMaxSum = kadane(arr)
				maxSum = max(maxSum, currMaxSum)
		return maxSum


class Solution:

	def maximumSumRectangle(self, m, n, mat):
		for i in range(m):
			for j in range(1, n):
				mat[i][j] += mat[i][j - 1]
		maxsum = float('-inf')
		for fc in range(n):
			for sc in range(fc, n):
				rowSum = [0] * m
				for r in range(m):
					rowSum[r] = mat[r][sc] - (mat[r][fc - 1] if fc > 0 else 0)
				cmax = 0
				for r in range(m):
					cmax = max(cmax + rowSum[r], rowSum[r])
					maxsum = max(maxsum, cmax)
		return maxsum


class Solution:

	def maximumSumRectangle(self, R, C, M):
		max_so_far = -1000000
		l = 0
		r = 0
		for l in range(0, C):
			sub = [0] * R
			for r in range(l, C):
				for i in range(0, len(sub)):
					sub[i] = sub[i] + M[i][r]
				currsum = 0
				for i in range(0, len(sub)):
					currsum = currsum + sub[i]
					if currsum > max_so_far:
						max_so_far = currsum
					if currsum < 0:
						currsum = 0
		return max_so_far


class Solution:

	def maximumSumRectangle(self, R, C, M):
		result = float('-inf')
		for left in range(C):
			row_sums = [0] * R
			for right in range(left, C):
				for row in range(R):
					row_sums[row] += M[row][right]
				curr_sum = row_sums[0]
				rectangle_sum = row_sums[0]
				for num in row_sums[1:]:
					curr_sum = max(curr_sum + num, num)
					rectangle_sum = max(rectangle_sum, curr_sum)
				result = max(result, rectangle_sum)
		return result


class Solution:

	def maximumSumRectangle(self, R, C, M):

		def kadanes(arr):
			cs = 0
			ms = arr[0]
			for a in arr:
				cs = max(a, cs + a)
				ms = max(ms, cs)
			return ms
		res = kadanes(M[0])
		for i in range(R):
			arr = [0] * C
			for r in range(i, -1, -1):
				for c in range(C):
					arr[c] += M[r][c]
				res = max(res, kadanes(arr))
		return res


class Solution:

	def maximumSumRectangle(self, R, C, M):

		def max_sub_arr(arr):
			s = ans = arr[0]
			for i in range(1, C):
				s += arr[i]
				s = max(s, arr[i])
				ans = max(ans, s)
			return ans
		ans = M[0][0]
		for k in range(R):
			a = [0] * C
			for i in range(k, R):
				for j in range(C):
					a[j] += M[i][j]
				ans = max(ans, max_sub_arr(a))
		return ans


class Solution:

	def kadane(self, arr, start, finish, n):
		Sum = 0
		maxSum = -999999999999
		i = None
		finish[0] = -1
		local_start = 0
		for i in range(n):
			Sum += arr[i]
			if Sum < 0:
				Sum = 0
				local_start = i + 1
			elif Sum > maxSum:
				maxSum = Sum
				start[0] = local_start
				finish[0] = i
		if finish[0] != -1:
			return maxSum
		maxSum = arr[0]
		start[0] = finish[0] = 0
		for i in range(1, n):
			if arr[i] > maxSum:
				maxSum = arr[i]
				start[0] = finish[0] = i
		return maxSum

	def maximumSumRectangle(self, ROW, COL, M):
		(maxSum, finalLeft) = (-999999999999, None)
		(finalRight, finalTop, finalBottom) = (None, None, None)
		(left, right, i) = (None, None, None)
		temp = [None] * ROW
		Sum = 0
		start = [0]
		finish = [0]
		for left in range(COL):
			temp = [0] * ROW
			for right in range(left, COL):
				for i in range(ROW):
					temp[i] += M[i][right]
				Sum = self.kadane(temp, start, finish, ROW)
				if Sum > maxSum:
					maxSum = Sum
					finalLeft = left
					finalRight = right
					finalTop = start[0]
					finalBottom = finish[0]
		return maxSum


def kadans(a):
	m = a[0]
	ans = a[0]
	for i in range(1, len(a)):
		ans = max(a[i], a[i] + ans)
		m = max(m, ans)
	return m

class Solution:

	def maximumSumRectangle(self, R, C, M):
		r = R
		c = C
		m = M
		maxsum = -999
		for cstart in range(c):
			sum = [0] * r
			for cend in range(cstart, c):
				for row in range(r):
					sum[row] += m[row][cend]
				currsum = kadans(sum)
				maxsum = max(maxsum, currsum)
		return maxsum


class Solution:

	def maximumSumRectangle(self, R, C, M):
		max_sum = -float('inf')
		for i in range(R):
			row_sum = [0] * C
			for j in range(i, R):
				for k in range(C):
					row_sum[k] += M[j][k]
				current_sum = 0
				for k in range(C):
					current_sum += row_sum[k]
					if current_sum > max_sum:
						max_sum = current_sum
					if current_sum < 0:
						current_sum = 0
		return max_sum


class Solution:

	def maximumSumRectangle(self, R, C, a):
		ans = a[0][0]
		for i in range(C):
			temp = [0] * R
			for j in range(i, C):
				for k in range(R):
					temp[k] += a[k][j]
				currSum = 0
				for r in range(R):
					currSum += temp[r]
					if ans < currSum:
						ans = currSum
					if currSum < 0:
						currSum = 0
		return ans


class Solution:

	def maxSubArray(self, nums):
		n = len(nums)
		chain = nums[0]
		ans = nums[0]
		for i in range(1, n):
			if nums[i] + chain > nums[i]:
				chain = nums[i] + chain
			else:
				chain = nums[i]
			ans = max(ans, chain)
		return ans

	def maximumSumRectangle(self, R, C, M):
		ans = -999999999999
		for start in range(R):
			temp = [0] * C
			for end in range(start, R):
				for j in range(C):
					temp[j] = temp[j] + M[end][j]
				res = self.maxSubArray(temp)
				ans = max(ans, res)
		return ans


from math import inf

class Solution:

	def maximumSumRectangle(self, R, C, M):
		glb_mx_rct_sum = -inf
		tmp_row_sum_arr = [0 for i in range(R)]
		for col_left in range(C):
			for col_right in range(col_left, C):
				for row in range(R):
					tmp_row_sum_arr[row] += M[row][col_right]
				(mx_rct_sum, curr_rct_sum) = (tmp_row_sum_arr[0], tmp_row_sum_arr[0])
				if col_right == C - 1:
					tmp_row_sum_arr[0] = 0
				for row in range(1, R):
					curr_rct_sum = max(curr_rct_sum + tmp_row_sum_arr[row], tmp_row_sum_arr[row])
					mx_rct_sum = max(mx_rct_sum, curr_rct_sum)
					if col_right == C - 1:
						tmp_row_sum_arr[row] = 0
				glb_mx_rct_sum = max(glb_mx_rct_sum, mx_rct_sum)
		return glb_mx_rct_sum


from sys import maxsize

def kadanealgo(arr, n):
	Sum = 0
	maxSum = -maxsize
	for i in range(n):
		Sum += arr[i]
		if maxSum < Sum:
			maxSum = Sum
		if Sum < 0:
			Sum = 0
	return maxSum

class Solution:

	def maximumSumRectangle(self, n, m, arr):
		maxSum = -maxsize
		temp = [0] * n
		for left in range(m):
			for i in range(n):
				temp[i] = 0
			for right in range(left, m):
				for i in range(n):
					temp[i] += arr[i][right]
				Sum = kadanealgo(temp, n)
				if maxSum < Sum:
					maxSum = Sum
		return maxSum


class Solution:

	def maximumSumRectangle(self, R, C, M):

		def kadanes(arr):
			currMax = float('-inf')
			currMaxHere = 0
			for num in arr:
				currMaxHere += num
				if currMax < currMaxHere:
					currMax = currMaxHere
				if currMaxHere < 0:
					currMaxHere = 0
			return currMax
		sums = []
		maxi = float('-inf')
		for sCol in range(0, C):
			sums = [0] * R
			for eCol in range(sCol, C):
				for row in range(R):
					sums[row] += M[row][eCol]
				res = kadanes(sums)
				maxi = max(maxi, res)
		return maxi


class Solution:

	def maximumSumRectangle(self, R, C, M):
		_mxsum = -10000000000
		for cbegin in range(C):
			cend = cbegin
			sm = [0] * R
			while cend < C:
				for r in range(R):
					sm[r] += M[r][cend]
				_mxsum = max(_mxsum, self.maxSubArray(sm))
				cend += 1
		return _mxsum

	def maxSubArray(self, A):
		ans = A[0]
		sm = 0
		for i in range(0, len(A)):
			sm = max(sm + A[i], A[i])
			ans = max(ans, sm)
		return ans


class Solution:

	def kadane(self, ans):
		curr = 0
		best = float('-inf')
		for val in ans:
			if curr <= 0:
				curr = val
			else:
				curr += val
			best = max(best, curr)
		return best

	def maximumSumRectangle(self, R, C, M):
		maxval = float('-inf')
		for i in range(R):
			ans = [0] * C
			for j in range(i, R):
				for k in range(C):
					ans[k] += M[j][k]
				maxval = max(maxval, self.kadane(ans))
		return maxval


from collections import defaultdict

class Solution:

	def maximumSumRectangle(self, R, C, M):
		maxi = M[0][0]
		for i in range(R):
			for j in range(1, C):
				M[i][j] += M[i][j - 1]
		for i in range(C):
			for j in range(i, C):
				sumi = M[0][j]
				if i > 0:
					sumi -= M[0][i - 1]
				maxi = max(maxi, sumi)
				for k in range(1, R):
					t = M[k][j]
					if i > 0:
						t -= M[k][i - 1]
					sumi = max(sumi + t, t)
					maxi = max(maxi, sumi)
		return maxi


class Solution:

	def maximumSumRectangle(self, R, C, M):

		def kadaneAlgo(arr):
			n = len(arr)
			if n == 0:
				return 0
			maxVal = -sys.maxsize
			Tsum = 0
			startingIndex = 0
			s = 0
			endingIndex = 0
			for i in range(n):
				Tsum += arr[i]
				if maxVal < Tsum:
					startingIndex = s
					endingIndex = i
					maxVal = Tsum
				if Tsum < 0:
					Tsum = 0
					s = i + 1
			return (maxVal, startingIndex, endingIndex)
		maxSum = -sys.maxsize
		finalLeftCol = -1
		finalRIghtCol = -1
		finalTop = -1
		finaBottom = -1
		for leftCol in range(C):
			temp = [0] * R
			for rightCol in range(leftCol, C):
				for i in range(R):
					temp[i] += M[i][rightCol]
				(summ, start, end) = kadaneAlgo(temp)
				if maxSum < summ:
					finalLeftCol = leftCol
					finalRightCol = rightCol
					finalTop = start
					finalBottom = end
					maxSum = summ
		return maxSum


class Solution:

	def maximumSumRectangle(self, R, C, matrix):
		(rows, cols) = (R, C)
		(maxsum, left, right, top, bottom) = (-float('inf'), 0, 0, 0, 0)
		temp = [0] * rows
		for left in range(cols):
			temp = [0] * rows
			for right in range(left, cols):
				for i in range(rows):
					temp[i] += matrix[i][right]
				cursum = 0
				for i in range(R):
					cursum += temp[i]
					maxsum = max(maxsum, cursum)
					cursum = max(cursum, 0)
		return maxsum


class Solution:

	def kadane(self, arr):
		mx = -10 ** 7
		su = 0
		for i in arr:
			su += i
			mx = max(su, mx)
			if su < 0:
				su = 0
		return mx

	def maximumSumRectangle(self, R, C, M):
		sol = -10 ** 7
		for row_start in range(R):
			comp_arr = [0] * C
			for row_end in range(row_start, R):
				for col in range(C):
					comp_arr[col] += M[row_end][col]
				sol = max(sol, self.kadane(comp_arr))
		return sol


class Solution:

	def kadane(self, arr):
		maxi = float('-inf')
		summ = 0
		for i in arr:
			summ += i
			maxi = max(summ, maxi)
			if summ < 0:
				summ = 0
		return maxi

	def maximumSumRectangle(self, n, m, arr):
		temp = [None] * n
		maxsum = float('-inf')
		for i in range(m):
			temp = [0] * n
			for j in range(i, m):
				for r in range(n):
					temp[r] += arr[r][j]
				maxi = ob.kadane(temp)
				maxsum = max(maxsum, maxi)
		return maxsum
		pass


def kadanes(A):
	summ = 0
	maxx = float('-inf')
	for i in range(len(A)):
		summ += A[i]
		maxx = max(maxx, summ)
		if summ < 0:
			summ = 0
	return maxx

class Solution:

	def maximumSumRectangle(self, R, C, M):
		ans = float('-inf')
		for i in range(R):
			v = [0] * C
			for j in range(i, R):
				for col in range(C):
					v[col] += M[j][col]
				ans = max(ans, kadanes(v))
		return ans


class Solution:

	def kadane(self, ans):
		(m, s) = (float('-inf'), 0)
		for i in range(len(ans)):
			s += ans[i]
			if s > m:
				m = s
			if s < 0:
				s = 0
		return m

	def maximumSumRectangle(self, R, C, M):
		m = float('-inf')
		for i in range(R):
			ans = [0] * C
			for j in range(i, R):
				for k in range(C):
					ans[k] += M[j][k]
				m = max(m, self.kadane(ans))
		return m


class Solution:

	def maximumSumRectangle(self, R, C, M):
		maxx = M[0][0]
		for start in range(R):
			list_l = [0] * C
			for end in range(start, R):
				for i in range(C):
					list_l[i] = list_l[i] + M[end][i]
				cur_max = 0
				maxx_loc = M[0][0]
				for i in range(C):
					cur_max += list_l[i]
					maxx_loc = max(maxx_loc, cur_max)
					if cur_max < 0:
						cur_max = 0
				maxx = max(maxx_loc, maxx)
		return maxx


class Solution:

	def maximumSumRectangle(self, R, C, arr):
		ans = arr[0][0]
		for Cstart in range(0, C):
			temp = [0] * R
			for Cend in range(Cstart, C):
				for k in range(R):
					temp[k] += arr[k][Cend]
				CurrSum = 0
				for i in range(R):
					CurrSum += temp[i]
					if ans < CurrSum:
						ans = CurrSum
					if CurrSum < 0:
						CurrSum = 0
		return ans


class Solution:

	def kadanes(self, arr):
		maxi = -1000000000.0
		summ = 0
		for i in range(len(arr)):
			summ += arr[i]
			maxi = max(maxi, summ)
			if summ < 0:
				summ = 0
		return maxi

	def maximumSumRectangle(self, r, c, a):
		maxSum = -1000000000.0
		for i in range(c):
			temp = [0] * r
			for j in range(i, c):
				for k in range(r):
					temp[k] += a[k][j]
				maxSum = max(maxSum, self.kadanes(temp))
		return maxSum


from sys import maxsize

class Solution:

	def solve(self, arr, n):
		maxsum = -maxsize
		currsum = 0
		for i in range(n):
			currsum += arr[i]
			maxsum = max(maxsum, currsum)
			if currsum < 0:
				currsum = 0
		return maxsum

	def maximumSumRectangle(self, R, C, M):
		maxArea = -maxsize
		for i in range(R):
			temp = [0] * C
			for j in range(i, R):
				for k in range(C):
					temp[k] += M[j][k]
				maxArea = max(self.solve(temp, C), maxArea)
		return maxArea


class Solution:

	def maximumSumRectangle(self, R, C, M):
		max_sum = float('-inf')
		for left in range(C):
			temp = [0] * R
			for right in range(left, C):
				for i in range(R):
					temp[i] += M[i][right]
				current_sum = max_subarray_sum(temp)
				max_sum = max(max_sum, current_sum)
		return max_sum

def max_subarray_sum(temp):
	max_sum = float('-inf')
	current_sum = 0
	for i in range(len(temp)):
		current_sum += temp[i]
		max_sum = max(max_sum, current_sum)
		if current_sum < 0:
			current_sum = 0
	return max_sum


import copy

class Solution:

	def maximumSumRectangle(self, R, C, M):
		self.n = R
		self.m = C
		prefix = self.get_prefix(M)
		Max = -float('inf')
		for (rno, row) in enumerate(prefix):
			Max = max(Max, self.kadanes(row, self.m))
			for j in range(rno):
				temp = []
				temprow = prefix[j]
				for k in range(self.m):
					temp.append(row[k] - temprow[k])
				Max = max(Max, self.kadanes(temp, self.m))
		return Max

	def kadanes(self, row, n):
		total = 0
		Max = -float('inf')
		for i in range(n):
			total += row[i]
			Max = max(Max, total)
			if total < 0:
				total = 0
		return Max

	def get_prefix(self, arr):
		temp = copy.deepcopy(arr)
		for i in range(1, self.n):
			for j in range(self.m):
				temp[i][j] += temp[i - 1][j]
		return temp


class Solution:

	def maximumSumRectangle(self, R, C, M):

		def kadane(temp, n):
			max_sum = 0
			curr_sum = 0
			for i in range(n):
				curr_sum += temp[i]
				max_sum = max(curr_sum, max_sum)
				if curr_sum < 0:
					curr_sum = 0
			return max_sum
		max_sum = 0
		for i in range(C):
			temp = [0] * R
			for j in range(i, C):
				for k in range(R):
					temp[k] += M[k][j]
				sum_ = kadane(temp, R)
				max_sum = max(sum_, max_sum)
		if max_sum == 0:
			max_sum = -1
		return max_sum


class Solution:

	def maximumSumRectangle(self, R, C, M):

		def kad(arr):
			m = -99999999
			up = 0
			for i in arr:
				up += i
				if m < up:
					m = up
				if up < 0:
					up = 0
			return m
		ans = -99999999
		for r in range(R):
			c = [0] * C
			for row in range(r, R):
				for col in range(C):
					c[col] += M[row][col]
				ans = max(ans, kad(c))
		return ans


import numpy as np

class Solution:

	def maximumSumRectangle(self, R, C, M):
		M = np.array(M)
		max_sum = -10 ** 9
		for left_col in range(0, C, 1):
			B = [0] * R
			for right_col in range(left_col, C, 1):
				for k in range(0, R, 1):
					B[k] += M[k][right_col]
				sum = self.kadane(B)
				max_sum = max(max_sum, sum)
		return max_sum

	def kadane(self, A):
		sum = 0
		max_sum = A[0]
		for i in A:
			sum += i
			if sum < 0:
				if i > max_sum:
					max_sum = i
				sum = 0
			elif sum > max_sum:
				max_sum = sum
		return max_sum


class Solution:

	def kadane(self, arr, n):
		dp = [x for x in arr]
		maxi = dp[0]
		for i in range(1, n):
			if dp[i] < dp[i - 1] + arr[i]:
				dp[i] = dp[i - 1] + arr[i]
			maxi = max(maxi, dp[i])
		return maxi

	def maximumSumRectangle(self, R, C, M):
		arr = [0 for x in range(R)]
		answer = -float('inf')
		for j in range(C):
			for i in range(R):
				arr[i] = M[i][j]
			answer = max(answer, self.kadane(arr, R))
			for k in range(j + 1, C):
				for i in range(R):
					arr[i] += M[i][k]
				answer = max(answer, self.kadane(arr, R))
		return answer


class Solution:

	def kadane(self, q):
		dp = [-float('inf')] * len(q)
		dp[0] = q[0]
		for i in range(1, len(q)):
			dp[i] = max(q[i], dp[i - 1] + q[i])
		return max(dp)

	def maximumSumRectangle(self, r, c, mat):
		ans = -float('inf')
		for i in range(r):
			q = [0] * c
			for j in range(i, r):
				q = [sum(x) for x in zip(q, mat[j])]
				ans = max(ans, self.kadane(q))
		return ans


class Solution:

	def maximumSumRectangle(self, R, C, M):

		def kaden(temp):
			curr = 0
			maxx = max(temp)
			for i in temp:
				curr += i
				maxx = max(maxx, curr)
				if curr <= 0:
					curr = 0
			return maxx
		maxx = float('-inf')
		for c in range(C):
			dp = [0 for i in range(R)]
			for i in range(c, C):
				for r in range(R):
					dp[r] = dp[r] + M[r][i]
				maxx = max(maxx, kaden(dp))
		return maxx


class Solution:

	def maximumSumRectangle(self, R, C, M):
		maxSum = -99999999
		for start in range(R):
			sum = [0 for i in range(C)]
			for end in range(start, R):
				for c in range(C):
					sum[c] += M[end][c]
				currSum = self.Kedane(sum)
				maxSum = max(currSum, maxSum)
		return maxSum

	def Kedane(self, arr):
		(maxSum, currSum) = (-99999999, 0)
		for i in range(len(arr)):
			currSum = max(arr[i], currSum + arr[i])
			maxSum = max(currSum, maxSum)
		return maxSum


class Solution:

	def maximumSumRectangle(self, R, C, M):

		def kadane(cols, start_finish, n):
			max_sum = -math.inf
			local_start = -1
			start_finish = [-1, -1]
			cur_sum = 0
			for i in range(n):
				cur_sum += cols[i]
				if cur_sum < 0:
					cur_sum = 0
					local_start = i + 1
				elif cur_sum > max_sum:
					start_finish = [local_start, i]
					max_sum = cur_sum
			if start_finish[-1] != -1:
				return max_sum
			max_sum = cols[0]
			local_start = 0
			start_finish = [0][0]
			for i in range(1, n):
				if max_sum < cols[i]:
					max_sum = cols[i]
					start_finish = [i, i]
			return max_sum
		(final_top, final_left, final_bottom, final_right) = (None, None, None, None)
		max_sum = -math.inf
		start_finish = [-1, -1]
		for left in range(C):
			cols = [0] * R
			for right in range(left, C):
				for i in range(R):
					cols[i] += M[i][right]
				cur_sum = kadane(cols, start_finish, R)
				if cur_sum > max_sum:
					max_sum = cur_sum
					(final_top, final_bottom) = start_finish
					final_left = left
					final_right = right
		return max_sum


class Solution:

	def maximumSubArray(self, A):
		curSum = 0
		ans = -float('inf')
		for i in A:
			curSum += i
			ans = max(ans, curSum)
			if curSum < 0:
				curSum = 0
		return ans

	def maximumSumRectangle(self, R, C, M):
		ans = -float('inf')
		for r1 in range(R):
			curRow = [0 for i in range(C)]
			for r2 in range(r1, R):
				for c in range(C):
					curRow[c] += M[r2][c]
				ans = max(ans, self.maximumSubArray(curRow))
		return ans


class Solution:

	def maximumSumRectangle(self, R, C, M):
		if M == 1 and C == 1:
			return M[0][0]
		for i in range(1, R):
			for j in range(C):
				M[i][j] += M[i - 1][j]
		arr = [0] * C
		max_area = float('-inf')
		for l in range(1, R + 1):
			for i in range(R - l + 1):
				for j in range(C):
					arr[j] = M[i + l - 1][j] - M[i - 1][j] if i - 1 >= 0 else M[i + l - 1][j]
				currsum = 0
				maxsum = float('-inf')
				for k in range(C):
					currsum += arr[k]
					if currsum > maxsum:
						maxsum = currsum
					if currsum < 0:
						currsum = 0
				if maxsum > max_area:
					max_area = maxsum
		return max_area


from math import *

class Solution:

	def maximumSumRectangle(self, R, C, M):

		def kadane(arr):
			(cur, prev) = (-inf, 0)
			for n in arr:
				prev += n
				if prev > cur:
					cur = prev
				if prev < 0:
					prev = 0
			return cur
		(rows, cols) = (len(M), len(M[0]))
		res = -inf
		for up in range(rows):
			arr = [0] * cols
			for down in range(up, rows):
				for c in range(cols):
					arr[c] += M[down][c]
				res = max(res, kadane(arr))
		return res


from math import *

class Solution:

	def maximumSumRectangle(self, R, C, M):

		def kadane(arr):
			(cur, prev) = (-inf, 0)
			for n in arr:
				prev += n
				if prev > cur:
					cur = prev
				if prev < 0:
					prev = 0
			return cur
		(rows, cols) = (len(M), len(M[0]))
		res = -inf
		for left in range(cols):
			arr = [0] * rows
			for right in range(left, cols):
				for r in range(rows):
					arr[r] += M[r][right]
				res = max(res, kadane(arr))
		return res


class Solution:

	def maximumSumRectangle(self, R, C, M):
		sum = []
		for i in range(R):
			sum.append([])
			for j in range(C):
				if i == 0:
					sum[i].append(M[0][j])
				else:
					sum[i].append(sum[i - 1][j] + M[i][j])
		max_sum = None
		for i in range(R):
			for j in range(R):
				if i <= j:
					temp = []
					if i != 0:
						for c_pos in range(C):
							temp.append(sum[j][c_pos] - sum[i - 1][c_pos])
					else:
						temp = sum[j]
					local_max = None
					current_sum = 0
					for pos in range(C):
						current_sum += temp[pos]
						if not local_max:
							local_max = current_sum
						local_max = max(current_sum, local_max)
						if current_sum <= 0:
							current_sum = 0
					if not max_sum:
						max_sum = local_max
					max_sum = max(max_sum, local_max)
		return max_sum


class Solution:

	def maximumSumRectangle(self, R, C, M):
		arr = [float('-inf')] * R
		maxSum = float('-inf')
		for cstart in range(0, C):
			arr = [0] * R
			for cend in range(cstart, C):
				for r in range(0, R):
					arr[r] += M[r][cend]
				cursum = self.kadane(arr)
				maxSum = max(cursum, maxSum)
		return maxSum

	def kadane(self, arr):
		curSum = 0
		maxSum = float('-inf')
		for i in range(0, len(arr)):
			curSum += arr[i]
			if curSum > maxSum:
				maxSum = curSum
			if curSum < 0:
				curSum = 0
		return maxSum


class Solution:

	def kadanes(self, arr, n):
		(s, maxi) = (arr[0], arr[0])
		for i in range(1, n):
			s += arr[i]
			s = max(s, arr[i])
			maxi = max(s, maxi)
		return maxi

	def maximumSumRectangle(self, R, C, M):
		res = M[0][0]
		for starti in range(R):
			subMatSum = [0 for _ in range(C)]
			for i in range(starti, R):
				for j in range(C):
					subMatSum[j] += M[i][j]
				res = max(res, self.kadanes(subMatSum, C))
		return res


class Solution:

	def maximumSumRectangle(self, R, C, M):
		cs = [[0] * (C + 1) for _ in range(R)]
		for r in range(R):
			for c in range(1, C + 1):
				cs[r][c] = M[r][c - 1] + cs[r][c - 1]
		max_sum = -float('inf')
		for right in range(C):
			for left in range(right + 1):
				cur_sum = 0
				max_sum_right_left = -float('inf')
				for row in range(R):
					cur_sum += cs[row][right + 1] - cs[row][left]
					max_sum_right_left = max(max_sum_right_left, cur_sum)
					if cur_sum < 0:
						cur_sum = 0
				max_sum = max(max_sum, max_sum_right_left)
		return max_sum


class Solution:

	def maximumSumRectangle(self, R, C, M):
		long = [[0 for i in range(C)] for j in range(R + 1)]
		long[1] = M[0]
		for i in range(1, R):
			for j in range(C):
				long[i + 1][j] += long[i][j] + M[i][j]
		m = -10 ** 9
		for i in range(1, R + 1):
			for x in range(i, R + 1):
				t = 0
				for y in range(C):
					t += long[x][y] - long[i - 1][y]
					m = max(m, t)
					if t < 0:
						t = 0
		return m


class Solution:

	def kadane(self, nums, n):
		sum_ = 0
		max_ = -1000000000000
		for i in range(n):
			sum_ = max(sum_ + nums[i], nums[i])
			max_ = max(sum_, max_)
		return max_

	def find_max(self, M, m, n, x):
		temp = [0 for _ in range(n)]
		for i in range(x, m):
			for j in range(n):
				temp[j] += M[i][j]
			temp_max = self.kadane(temp, n)
			self.max_ = max(self.max_, temp_max)
		return

	def maximumSumRectangle(self, R, C, M):
		self.max_ = -100000000000
		for i in range(R):
			self.find_max(M, R, C, i)
		return self.max_


class Solution:

	def maximumSumRectangle(self, R, C, M):
		colSumMatrix = [[0] * C for _ in range(R)]
		for c in range(C):
			curr = 0
			for r in range(R):
				curr += M[r][c]
				colSumMatrix[r][c] = curr
		ans = -float('inf')
		for r1 in range(R):
			for r2 in range(r1, R):
				curr = 0
				for c in range(C):
					curr += colSumMatrix[r2][c] - (colSumMatrix[r1 - 1][c] if r1 > 0 else 0)
					ans = max(ans, curr)
					if curr < 0:
						curr = 0
		return ans