maxSubmatrixVersion2

Cho ma trận số nguyên N x M và số nguyên K. Tìm ma trận con kích thước K x K sao cho tổng giá trị các phần tử là lớn nhất, trả về giá trị lớn nhất đó.

Ví dụ:

• Với inMatrix = [[1, 1, 1],[2, -3, 2],[3, 3, 3],[-4, 7, 4],[-2, 9, 5]] và K=3 thì kết quả sẽ là maxSub(inMatrix)=28.

Ma trận đầu vào được biểu diễn như sau:

Với K=3 thì ta sẽ có 3 ma trận con có kích thước 3x3 là:

	Tổng các phần tử của ma trận này là: 13
	Tổng các phần tử của ma trận này là: 17
	Tổng các phần tử của ma trận này là: 28

Ma trận con có tổng các phần tử bằng 28 là ma trận có tổng lớn nhất, nên kết quả là 28.

Đầu vào/Đầu ra :

• [Giới hạn thời gian chạy] 0.5s với C++, 3s với Java và C#, 4s với Python, Go và JavaScript
• [Đầu vào] Matrix.Integer inMatrix
  Ma trận đầu vào kích thước N x M
2 < n,m < 104
• [Đầu vào] Integer K
  1 ≤ k ≤ min(n,m)
• [Đầu ra] int
  tổng ma trận K x K lớn nhất