Задача на логику из собеседования в Amazon

Разбираем задачу из собеседования в Amazon на middle разработчика в Берлин. Главное в ней — это придумать решение, а сам код пишется буквально в несколько строчек.

Задача

Дан двухмерный массив из чисел. Можно взять два соседний числа и умножить на -1. Нужно преобразовать матрицу так, чтобы сумма всех ее элементов была максимальной.