Flip, найти максимальную сумму матрицы путем умножения линий и столбиков на Опции

[DarkWishmaster]

Привет. Вот интересная задача:
Дана матрица NxM где её элементы положитнльные и отрицательные числа. Можно умножить сколько раз угодно любую линию и любой столбик на -1. Найдите максимальную суму чисел из матрицы которая может получиться путем этих умножений.
Например:
5 3
4 -2 2
3 -1 5
2 0 -3
4 1 -3
5 -3 2
Умножаем 3 линию и 2 столбик. Сума=28.
Есть идеи как это вообще сделать?
Сначала я думал что можно пройтись по линиям и столбикам и если по модулю сума отрицательных чисел больше положительных то умножаем на -1, но такой способ не помогает так как когда мы умножаем линию то изменются и колоны и наоборот.

[IUnknown]

нашел одно решение (100/100), вроде он тут только по столбикам идет.

Вот и спрашивай у автора этого решения. Я в чужом копаться не собираюсь. Мне интереснее свое написать...

Кстати, если тебе надо онлайн-тесты проходить - это надо заранее указывать, я вообще бы к таким задачам не прикасался. Мало того, что решает один, а сдает - другой, так еще и не пойми какие ограничения, и по размеру, и по времени... Короче, зря написал код... Больше не повторится...