返回一个二维数组中，子矩阵最大累加和。
根据昨天的每日一题计算出0 ~ 0行，0 ~ 1行，0 ~ 2行，……0~N行的子数组最大累加和。
根据昨天的每日一题计算出1 ~ 1行，1 ~ 2行，1 ~ 3行，……1~N行的子数组最大累加和。
根据昨天的每日一题计算出2 ~ 2行，2 ~ 3行，2 ~ 4行，……2~N行的子数组最大累加和。
……
最后取最大值做返回值。
时间复杂度：O(N^2 * M)。
代码用golang编写。代码如下：
package main
import (
"fmt"
"math"
)
func main() {
m := [][]int{{1, 2}, {3, -40}}
ret := maxSum(m)
fmt.Println(ret)
}
func maxSum(m [][]int) int {
if len(m) == 0 || len(m[0]) == 0 {
return 0
}
// O(N^2 * M)
N := len(m)
M := len(m[0])
max := math.MinInt64
for i := 0; i < N; i++ {
// i~j
s := make([]int, M)
for j := i; j < N; j++ {
for k := 0; k < M; k++ {
s[k] += m[j][k]
}
max = getMax(max, maxSubArray(s))
}
}
return max
}
func maxSubArray(arr []int) int {
if len(arr) == 0 {
return 0
}
N := len(arr)
ans := arr[0]
pre := arr[0]
for i := 1; i < N; i++ {
pre = getMax(arr[i], pre+arr[i])
ans = getMax(ans, pre)
}
return ans
}
func getMax(a int, b int) int {
if a > b {
return a
} else {
return b
}
}执行结果如下：
