[C++] Single-pass Solution Explained, ~100% Time, ~96% Space
Cute one that really rewards quick thinking over rote memorisation of algos and other tricks.\n\nGiven the constraints, it is pretty clear that we canNOT even b
Cute one that really rewards quick thinking over rote memorisation of algos and other tricks.\n\nGiven the constraints, it is pretty clear that we canNOT even begin to attempt computing all the permutations of how we might flip pairs of cells. But the point is that we really should not care!\n\nDon\'t believe me? Bear with me as I explain my thought process!\n\nLet\'s start with a simple consideration: if all numbers were non-negative, we might get away with it just summing each cell - that I guess is pretty clear and it also gives us a lower bound: we can\'t do less than linear time here!\n\nNow, what happens if we have negative numbers?\n\nSince there is no limit to how many times we can flip cell, we can demonstrate that given an arbirtrarily large matrix `m`, we can always end up flipping cells in pairs so that we can would end up with `1` negative cell (if the initial amount of negative cells was odd) or `0` (if the initial amount of them was even) - try to think about it by induction.\n\nAnd, in the former case, what element should we keep negative? But of course the one with the lesser absolute value!\n\nNow, having cells with value of `0` would seem to complicate things a bit, but not even that much: after all, if we have even just one `0`, we know that we can just keep summing without a care, since we can just finish having a `0` cell flipped to `0` with no change whatsoever :)\n\nOkay, enough description - time to code and as usual we will start with declaring our support variables:\n* `res` will be our accumulator variable, storing our ongoing sum of cells, preset to `0`;\n* `flippables` will keep track of all the non-positive numbers (yes, `0`s and negatives will be bucketed together here), initially set to `0`;\n* `smallest` will keep track of the smallest element (in absolute value) we have seen so far, initially set to `INT_MIN`.\n\nWe will then loop through each `row` of `matrix` (taken as a reference, of course) and through each value `n` of `row` and deal with 2 base cases:\n* if `n <= 0`, we will:\n\t* increase `flippables` by `1`;\n\t* update `smallest` to be the minimum absolute value between its current one and `n` (and since we know both are always going to be non positive numbers, we can do so by merely using `max`, with no need of swapping signs);\n\t* increase `res` by `-n` (ie: adding its absolute value);\n* otherwise, we will:\n\t* increase `res` by `n`;\n\t* update `smallest` by the maximum between its current value and `-n` - because, yes, we might wish to flip even an initially positive number, if its absolute value is lesser than any other negative number encountered so far.\n\nOnce done, we can just `return` `res` plus `smallest` if `flippables` was odd or plus `0` otherwise :)\n\nThe code:\n\n```cpp\nclass Solution {\npublic:\n    long long maxMatrixSum(vector<vector<int>>& matrix) {\n        // support variables\n        long long res = 0;\n        int flippables = 0, smallest = INT_MIN;\n        // parsing matrix\n        for (auto &row: matrix) {\n            for (int n: row) {\n                // flippable cells (non positive)\n                if (n <= 0) {\n                    flippables++;\n                    smallest = max(smallest, n);\n                    res -= n;\n                }\n                // non flipppable cells (positive)\n                else {\n                    res += n;\n                    smallest = max(smallest, -n);\n                }\n            }\n        }\n        return res + (flippables & 1 ? smallest * 2 : 0);\n    }\n};\n```\n# Brag\n![image.png](https://assets.leetcode.com/users/images/059761ea-99ec-43d5-8758-cde57d5faca4_1732532887.491503.png)\n
['Array', 'C', 'C++']