2021-06-15：返回一个二维数组中，子矩阵最大累加和。

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
    }
}