题目描述
给定一个正整数和负整数组成的 N × M 矩阵，编写代码找出元素总和最大的子矩阵。
返回一个数组 [r1, c1, r2, c2]，其中 r1, c1 分别代表子矩阵左上角的行号和列号，r2, c2 分别代表右下角的行号和列号。若有多个满足条件的子矩阵，返回任意一个均可。
注意：本题相对书上原题稍作改动
示例:
输入:
[
[-1,0],
[0,-1]
]
输出: [0,1,0,1]
解释: 输入中标粗的元素即为输出所表示的矩阵
说明：
1 <= matrix.length, matrix[0].length <= 200
解法
方法一
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29 | class Solution:
def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:
m, n = len(matrix), len(matrix[0])
s = [[0] * n for _ in range(m + 1)]
for i in range(m):
for j in range(n):
# 构造列前缀和
s[i + 1][j] = s[i][j] + matrix[i][j]
mx = matrix[0][0]
ans = [0, 0, 0, 0]
for i1 in range(m):
for i2 in range(i1, m):
nums = [0] * n
for j in range(n):
nums[j] = s[i2 + 1][j] - s[i1][j]
start = 0
f = nums[0]
for j in range(1, n):
if f > 0:
f += nums[j]
else:
f = nums[j]
start = j
if f > mx:
mx = f
ans = [i1, start, i2, j]
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36 | class Solution {
public int[] getMaxMatrix(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
int[][] s = new int[m + 1][n];
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
s[i + 1][j] = s[i][j] + matrix[i][j];
}
}
int mx = matrix[0][0];
int[] ans = new int[] {0, 0, 0, 0};
for (int i1 = 0; i1 < m; ++i1) {
for (int i2 = i1; i2 < m; ++i2) {
int[] nums = new int[n];
for (int j = 0; j < n; ++j) {
nums[j] = s[i2 + 1][j] - s[i1][j];
}
int start = 0;
int f = nums[0];
for (int j = 1; j < n; ++j) {
if (f > 0) {
f += nums[j];
} else {
f = nums[j];
start = j;
}
if (f > mx) {
mx = f;
ans = new int[] {i1, start, i2, j};
}
}
}
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37 | class Solution {
public:
vector<int> getMaxMatrix(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
vector<vector<int>> s(m + 1, vector<int>(n));
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
s[i + 1][j] = s[i][j] + matrix[i][j];
int mx = matrix[0][0];
vector<int> ans(4);
for (int i1 = 0; i1 < m; ++i1) {
for (int i2 = i1; i2 < m; ++i2) {
vector<int> nums;
for (int j = 0; j < n; ++j)
nums.push_back(s[i2 + 1][j] - s[i1][j]);
int start = 0;
int f = nums[0];
for (int j = 1; j < n; ++j) {
if (f > 0)
f += nums[j];
else {
f = nums[j];
start = j;
}
if (f > mx) {
mx = f;
ans[0] = i1;
ans[1] = start;
ans[2] = i2;
ans[3] = j;
}
}
}
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37 | func getMaxMatrix(matrix [][]int) []int {
m, n := len(matrix), len(matrix[0])
s := make([][]int, m+1)
for i := range s {
s[i] = make([]int, n)
}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
s[i+1][j] = s[i][j] + matrix[i][j]
}
}
mx := matrix[0][0]
ans := make([]int, 4)
for i1 := 0; i1 < m; i1++ {
for i2 := i1; i2 < m; i2++ {
var nums []int
for j := 0; j < n; j++ {
nums = append(nums, s[i2+1][j]-s[i1][j])
}
start := 0
f := nums[0]
for j := 1; j < n; j++ {
if f > 0 {
f += nums[j]
} else {
f = nums[j]
start = j
}
if f > mx {
mx = f
ans = []int{i1, start, i2, j}
}
}
}
}
return ans
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40 | class Solution {
func getMaxMatrix(_ matrix: [[Int]]) -> [Int] {
let m = matrix.count, n = matrix[0].count
var s = Array(repeating: Array(repeating: 0, count: n), count: m + 1)
for i in 0..<m {
for j in 0..<n {
s[i + 1][j] = s[i][j] + matrix[i][j]
}
}
var mx = matrix[0][0]
var ans = [0, 0, 0, 0]
for i1 in 0..<m {
for i2 in i1..<m {
var nums = [Int](repeating: 0, count: n)
for j in 0..<n {
nums[j] = s[i2 + 1][j] - s[i1][j]
}
var start = 0
var f = nums[0]
for j in 1..<n {
if f > 0 {
f += nums[j]
} else {
f = nums[j]
start = j
}
if f > mx {
mx = f
ans = [i1, start, i2, j]
}
}
}
}
return ans
}
}
|