题解 | #最大子矩阵#

package main



/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param matrix int整型二维数组
 * @return int整型
 */
func getMaxMatrix(matrix [][]int) int {
	/*
	   dp
	   题解：
	   首先，最大子矩阵和最小子矩阵是同一回事。
	   我们先求出矩阵每一列的前缀和sum[i][j],i为列号，j为行号，然后枚举一个开始的行和一个结束的行，
	   然后问题就转化成了最大子数组问题，最大子数组的前缀和就是sum[j][ed]-sum[j][st-1]
	   最大子数组的解法就是遍历一遍数组，如果当前数字和为正数，就更新答案，如果为负数，则从下一个位置开始重新求和。
	*/
	n := len(matrix)
	m := len(matrix[0])
	ans := matrix[0][0]

	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if matrix[i][j] < ans {
				ans = matrix[i][j]
			}
		}
	}

	mostmin := ans
	for i := 0; i < n; i++ {
		help := make([]int, m)
		for row := i; row < n; row++ {
			for col := 0; col < m; col++ {
				help[col] = help[col] + matrix[row][col]
			}

			cursum := f(help, mostmin)
			if cursum > ans {
				ans = cursum
			}
		}
	}
	return ans

}

func f(arr []int, ans int) int {
	//ans := math.MinInt
	tmp := 0

	for i := 0; i < len(arr); i++ {
		if tmp > 0 {
			tmp += arr[i]
		} else {
			tmp = arr[i]
		}

		if tmp > ans {
			ans = tmp
		}
	}
	return ans
}