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, но такой способ не помогает так как когда мы умножаем линию то изменются и колоны и наоборот.

[Krjuger]

Самый простой вариант сделать полный перебор)))Но производительность будет аховая....
Насамом деле я думаю,если внести в твою идею некоторые корректировки,то что то путное выйдет.Смотри у тебя есть 2 варианта,либо ты умножаеш строку либо столбец.Как варант,ты находиш максимальную сууму в строке,Если надо изменить всю строку,то ты меняеш и ничего не делаеш со столбцами,если чтобы достигнуть максимума тебе в строке надо изменить 1 или 2 элемента(я отталкиваюсь от твоей матрици),то ты совершаеш эти действия для подматрицы без первой строки и дальше смотриш,если разница сумм исходной и измененной подматриц больше нуля,то ты применяеш изменения для исходной матрици,если меньше нуля,то сравниваеш это число и тем,на сколько больше нам удалось получить от изменени в первой строке,если все таки первая строка нам позволит увеличить сумму то применяеш,если нет,то отменяеш изменения и переходиш на 2 строку и все аналогично.

Больше пока что ничего в голову не лезет.Задача явно переборная и надо максимально сократить этот перебор.У моего варианта достаточно много минусов,постараюсь придумать вариант получше.