Given an N x N matrix, mat[N][N] of integers. The task is to find the maximum value of mat(c, d) mat(a, b) over all choices of indexes such that both c > a and d > b.
Example 1:
Input:
mat[N][N] = {{ 1, 2, -1, -4, -20 },
             { -8, -3, 4, 2, 1 }, 
             { 3, 8, 6, 1, 3 },
             { -4, -1, 1, 7, -6 },
             { 0, -4, 10, -5, 1 }};
Output: 18
Explanation: The maximum value is 18 as mat[4][2] 
- mat[1][0] = 18 has maximum difference.
 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function findMaxValue() which takes a matrix mat and returns an integer as output.
Expected Time Complexity: O(N^{2})
Expected Auxiliary Space: O(N^{2})
 
Constraints:
1 <= N <= 10^{3}
-10^{3}<= mat[i][j] <=10^{3}

Source: geeksforgeeks | Difficulty: MEDIUM_HARD

Starter code: from typing import List





class Solution:

    def findMaxValue(self, n : int, mat : List[List[int]]) -> int:

        # code here

        



Solutions:
from typing import List

class Solution:

	def findMaxValue(self, n: int, mat: List[List[int]]) -> int:
		if n == 1:
			return 0
		ans = -10 ** 10
		dp = [[0 for i in range(n)] for j in range(n)]
		dp[0][0] = mat[0][0]
		for i in range(1, n):
			dp[i][0] = min(dp[i - 1][0], mat[i][0])
			dp[0][i] = min(dp[0][i - 1], mat[0][i])
		for i in range(1, n):
			for j in range(1, n):
				temp = mat[i][j]
				dp[i][j] = min(dp[i][j - 1], dp[i - 1][j], mat[i][j])
				ans = max(ans, temp - dp[i - 1][j - 1])
		return ans


from typing import List

class Solution:

	def findMaxValue(self, n: int, mat: List[List[int]]) -> int:
		minMat = [[0 for c in range(n)] for r in range(n)]
		minMat[0][0] = mat[0][0]
		for i in range(1, n):
			minMat[0][i] = min(minMat[0][i - 1], mat[0][i])
			minMat[i][0] = min(minMat[i - 1][0], mat[i][0])
		for r in range(1, n):
			for c in range(1, n):
				minMat[r][c] = min(minMat[r - 1][c], minMat[r][c - 1], mat[r][c])
		maxMat = [[0 for c in range(n)] for r in range(n)]
		maxMat[n - 1][n - 1] = mat[n - 1][n - 1]
		for i in range(n - 2, -1, -1):
			maxMat[n - 1][i] = max(maxMat[n - 1][i + 1], mat[n - 1][i])
			maxMat[i][n - 1] = max(maxMat[i + 1][n - 1], mat[i][n - 1])
		for r in range(n - 2, -1, -1):
			for c in range(n - 2, -1, -1):
				maxMat[r][c] = max(maxMat[r][c + 1], maxMat[r + 1][c], mat[r][c])
		ans = float('-inf')
		for r in range(n - 1):
			for c in range(n - 1):
				ans = max(ans, maxMat[r + 1][c + 1] - minMat[r][c])
		return ans


from typing import List

class Solution:

	def findMaxValue(self, n: int, mat: List[List[int]]) -> int:
		min_mat = [[0 for _ in range(n)] for _ in range(n)]
		min_mat[0][0] = mat[0][0]
		for i in range(1, n):
			min_mat[i][0] = min(min_mat[i - 1][0], mat[i][0])
		for i in range(1, n):
			min_mat[0][i] = min(min_mat[0][i - 1], mat[0][i])
		for i in range(1, n):
			for j in range(1, n):
				min_mat[i][j] = min(mat[i][j], min(min_mat[i - 1][j], min_mat[i][j - 1]))
		ans = [[0 for _ in range(n)] for _ in range(n)]
		max_val = float('-inf')
		for i in range(n - 1, 0, -1):
			for j in range(n - 1, 0, -1):
				ans[i][j] = mat[i][j] - min_mat[i - 1][j - 1]
				max_val = max(max_val, ans[i][j])
		return max_val


from typing import List

class Solution:

	def findMaxValue(self, n: int, mat: List[List[int]]) -> int:
		ans = -1 * int(1000000000.0)
		for i in range(1, n):
			mat[i][0] = min(mat[i][0], mat[i - 1][0])
			mat[0][i] = min(mat[0][i], mat[0][i - 1])
		for i in range(1, n):
			for j in range(1, n):
				ans = max(ans, mat[i][j] - mat[i - 1][j - 1])
				mat[i][j] = min(mat[i][j], min(mat[i][j - 1], mat[i - 1][j]))
		return ans


from typing import List

class Solution:

	def findMaxValue(self, n: int, mat: List[List[int]]) -> int:
		r = len(mat)
		c = len(mat[0])
		mx = mat[-1][-1]
		for i in range(r - 1, -1, -1):
			mx = max(mx, mat[i][-1])
			mat[i][-1] = mx
		mx = mat[-1][-1]
		for j in range(c - 1, -1, -1):
			mx = max(mx, mat[-1][j])
			mat[-1][j] = mx
		ans = -10000000
		for i in range(r - 2, -1, -1):
			for j in range(c - 2, -1, -1):
				ans = max(ans, mat[i + 1][j + 1] - mat[i][j])
				mat[i][j] = max([mat[i][j], mat[i + 1][j], mat[i][j + 1]])
		return ans


from typing import List
import sys

class Solution:

	def findMaxValue(self, N: int, mat: List[List[int]]) -> int:
		maxValue = -sys.maxsize - 1
		maxArr = [[0 for x in range(N)] for y in range(N)]
		maxArr[N - 1][N - 1] = mat[N - 1][N - 1]
		maxv = mat[N - 1][N - 1]
		for j in range(N - 2, -1, -1):
			if mat[N - 1][j] > maxv:
				maxv = mat[N - 1][j]
			maxArr[N - 1][j] = maxv
		maxv = mat[N - 1][N - 1]
		for i in range(N - 2, -1, -1):
			if mat[i][N - 1] > maxv:
				maxv = mat[i][N - 1]
			maxArr[i][N - 1] = maxv
		for i in range(N - 2, -1, -1):
			for j in range(N - 2, -1, -1):
				if maxArr[i + 1][j + 1] - mat[i][j] > maxValue:
					maxValue = maxArr[i + 1][j + 1] - mat[i][j]
				maxArr[i][j] = max(mat[i][j], max(maxArr[i][j + 1], maxArr[i + 1][j]))
		return maxValue


from typing import List

class Solution:

	def findMaxValue(self, n: int, mat: List[List[int]]) -> int:
		res = -2 ** 31
		dp = [[-2 ** 31 for i in range(len(mat[0]))] for i in range(len(mat))]
		for i in range(n - 1, -1, -1):
			for j in range(n - 1, -1, -1):
				a = -2 ** 31
				if i + 1 < n:
					a = max(a, dp[i + 1][j])
				if j + 1 < n:
					a = max(a, dp[i][j + 1])
				if i + 1 < n and j + 1 < n:
					a = max(a, mat[i + 1][j + 1])
				dp[i][j] = a
				res = max(res, a - mat[i][j])
		return res


from typing import List

class Solution:

	def findMaxValue(self, n: int, mat: List[List[int]]) -> int:
		matcopy = [[-10 ** 9] * n for i in range(n)]
		for i in range(n):
			for j in range(n):
				matcopy[i][j] = mat[i][j]
		for j in range(n - 2, -1, -1):
			matcopy[n - 1][j] = max(matcopy[n - 1][j + 1], matcopy[n - 1][j])
		for i in range(n - 2, -1, -1):
			matcopy[i][n - 1] = max(matcopy[i + 1][n - 1], matcopy[i][n - 1])
		for i in range(n - 2, -1, -1):
			for j in range(n - 2, -1, -1):
				matcopy[i][j] = max(matcopy[i][j], matcopy[i][j + 1], matcopy[i + 1][j])
		ans = -10 ** 9
		for i in range(n - 1):
			for j in range(n - 1):
				ans = max(ans, matcopy[i + 1][j + 1] - mat[i][j])
		return ans


from typing import List

class Solution:

	def findMaxValue(self, n: int, mat: List[List[int]]) -> int:
		R = -float('inf')
		for i in range(1, n):
			mat[0][i] = min(mat[0][i], mat[0][i - 1])
			mat[i][0] = min(mat[i][0], mat[i - 1][0])
		for i in range(1, n):
			for j in range(1, n):
				x = mat[i][j]
				mat[i][j] = min(x, min(mat[i - 1][j], mat[i][j - 1]))
				R = max(R, x - mat[i - 1][j - 1])
		return R


from typing import List

class Solution:

	def findMaxValue(self, n: int, mat: List[List[int]]) -> int:
		for i in range(1, n):
			mat[i][0] = min(mat[i - 1][0], mat[i][0])
			mat[0][i] = min(mat[0][i - 1], mat[0][i])
		maxi = -10 ** 9
		for i in range(1, n):
			for j in range(1, n):
				if mat[i][j] - mat[i - 1][j - 1] > maxi:
					maxi = mat[i][j] - mat[i - 1][j - 1]
				mat[i][j] = min(min(mat[i][j], mat[i - 1][j - 1]), min(mat[i - 1][j], mat[i][j - 1]))
		return maxi

class IntMatrix:

	def __init__(self) -> None:
		pass

	def Input(self, n, m):
		matrix = []
		for _ in range(n):
			matrix.append([int(i) for i in input().strip().split()])
		return matrix

	def Print(self, arr):
		for i in arr:
			for j in i:
				print(j, end=' ')
			print()
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		mat = IntMatrix().Input(n, n)
		obj = Solution()
		res = obj.findMaxValue(n, mat)
		print(res)


from typing import List

class Solution:

	def findMaxValue(self, n: int, mat: List[List[int]]) -> int:
		inf = float('inf')
		ans = -inf
		grid = [-inf] * n
		for i in range(n - 2, -1, -1):
			for j in range(n - 2, -1, -1):
				grid[j] = max(grid[j], mat[i + 1][j + 1], grid[j + 1])
				ans = max(ans, grid[j] - mat[i][j])
		return ans