package main

func maximalRectangle(matrix [][]byte) (maxArea int) {
	if len(matrix) == 0 {
		return
	}
	hei := make([]int, len(matrix[0]))
	for i := 0; i < len(matrix); i++ {
		for j := 0; j < len(matrix[0]); j++ {
			if matrix[i][j] == '1' {
				hei[j]++
			} else {
				hei[j] = 0
			}
		}
		// Now we can find the max rectangle in the hist :)
		st := make([]int, 0)
		k, l := 0, 0
		for k < len(hei) {
			if l == 0 || hei[k] >= hei[st[l-1]] {
				st = append(st, k)
				k, l = k+1, l+1
			} else {
				t := st[l-1]
				st = st[:l-1]
				l--
				var area int
				if l == 0 {
					area = hei[t] * k
				} else {
					area = hei[t] * (k - st[l-1] - 1)
				}
				if area > maxArea {
					maxArea = area
				}
			}
		}
		for l != 0 {
			t := st[l-1]
			st = st[:l-1]
			l--
			var area int
			if l == 0 {
				area = hei[t] * k
			} else {
				area = hei[t] * (k - st[l-1] - 1)
			}
			if area > maxArea {
				maxArea = area
			}
		}
	}
	return
}

// func main() {
// 	m := [][]byte{
// 		{'1', '0', '1', '0', '0'},
// 		{'1', '0', '1', '1', '1'},
// 		{'1', '1', '1', '1', '1'},
// 		{'1', '0', '0', '1', '0'}}
// 	println(maximalRectangle(m))
// 	m = [][]byte{
// 		{'1', '0', '1', '0'},
// 		{'1', '0', '1', '1'},
// 		{'1', '0', '1', '1'},
// 		{'1', '1', '1', '1'}}
// 	println(maximalRectangle(m))
// }