最大正方形

package main

import "fmt"

func maximalSquare(matrix [][]byte) int {
    if len(matrix) == 0 || len(matrix[0]) == 0 {
        return 0
    }

    rows, cols := len(matrix), len(matrix[0])
    dp := make([][]int, rows)
    maxSide := 0

    for i := range dp {
        dp[i] = make([]int, cols)
        for j := range dp[i] {
            dp[i][j] = int(matrix[i][j] - '0')
            if dp[i][j] == 1 {
                maxSide = 1 // 初始化最大边长为1
            }
        }
    }

    for i := 1; i < rows; i++ {
        for j := 1; j < cols; j++ {
            if dp[i][j] == 1 {
                dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1])) + 1
                maxSide = max(maxSide, dp[i][j])
            }
        }
    }

    return maxSide * maxSide
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func main() {
    matrix := [][]byte{
        {'1', '0', '1', '0', '0'},
        {'1', '0', '1', '1', '1'},
        {'1', '1', '1', '1', '1'},
        {'1', '0', '0', '1', '0'},
    }

    area := maximalSquare(matrix)
    fmt.Printf("最大正方形的面积是：%d\n", area)
}