defmodule Solution do
def max_sum_submatrix(matrix, k) do
{row, col, matrix} = to_map(matrix, 0, 0, %{})
for c1 <- 0..(col - 1), reduce: -100_001 do
result ->
for c2 <- c1..0, reduce: {[], result} do
{rows, result} ->
rows =
case rows do
[] ->
for r <- 0..(row - 1), do: Map.get(matrix, {r, c2})
rs ->
calculate_presum(rs, 0, c2, matrix, [])
end
case larget_close_to_k(rows, :gb_sets.singleton(0), 0, nil, k) do
nil -> {rows, result}
res -> {rows, max(result, res)}
end
end
|> elem(1)
end
end
defp to_map([], row, col, map), do: {row, col, map}
defp to_map([[x]], row, col, map), do: {row + 1, col + 1, Map.put(map, {row, col}, x)}
defp to_map([[] | rest], row, _col, map), do: to_map(rest, row + 1, 0, map)
defp to_map([[x | r_rest] | rest], row, col, map),
do: to_map([r_rest | rest], row, col + 1, Map.put(map, {row, col}, x))
defp calculate_presum([], _row, _col, _matrix, res), do: Enum.reverse(res)
defp calculate_presum([x | rest], row, col, matrix, res),
do:
calculate_presum(rest, row + 1, col, matrix, [
x + Map.get(matrix, {row, col}) | res
])
defp larget_close_to_k([], _sums, _sum, res, _k), do: res
defp larget_close_to_k([x | rest], sums, sum, res, k) do
sum = sum + x
iter = :gb_sets.iterator_from(sum - k, sums)
res =
case :gb_sets.next(iter) do
{val, _} ->
if res == nil do
sum - val
else
max(res, sum - val)
end
_ ->
res
end
larget_close_to_k(rest, :gb_sets.add(sum, sums), sum, res, k)
end
end