simple py,JAVA code explained!! (Math+greedy+matrix)
Problem understanding\n\n- They have given us a matrix of n*n.The matrix contains both +ve and -ve numbers.\n- we need to maximise the sum of all elements in th
# Problem understanding\n\n- They have given us a `matrix` of `n*n`.The matrix contains both *+ve* and *-ve* numbers.\n- we need to ***maximise*** the *sum of all elements* in the matrix.\n- we can perform the following operation any number of times in the given 2 adjacent cells.\n- **OPERATION:** we can multiply 2 neighbours with `-1`.\n- **NOTE:** on careful analysis we can see that,if we have `totalNumberOfNegative` numbers as **EVEN** then we can convert the entire matrix with **ZERO** negative value and if we have **ODD** we end up with **ONE** negative value.\n```\n//Even number of -ve Number\n 2  -4   6       -2   4   6         2   4   6\n-8   0   8 ----> -8   0   8 ----->  8   0   8\n 4  -6  -2        4   6   2         4   6   2\n```\n```\n//Odd number of -ve Number\n 2  -4  -6       -2   4   6         2   4   6\n-8   0   8 ----> -8   0  -8 ----->  8   0   8\n 4  -6  -2        4   6   2         4   6   2\n```\n- The above is a key point,now try solving it on your own!\n \n---\n\n\n\n# Approach:Math+greedy\n<!-- Describe your approach to solving the problem. -->\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n- As we have to maximise the sum of `matrix` we wil find absolute sum of `matrix` and store it in `sum` ,meanwhile we will count the number of negative values in `matrix` and store it in `negativecount`.\n- Now we know we can get 2 possible case wrt `negativecount`.\n  - If it is *odd* then we can say we can manupulate the entire matrix such that there is only single negative number exist.\n  - If it is *even* then no problem we can manupulate the entire matrix taht conatisn only +ve integers.\n- If the `negativecount` is odd then we should try to maximise the `sum` so we give the `-ve` value to the `smallest` value in the given matrix(absolute smallest[smallest in both `+ve` and `-ve` number]).we store it in `absMin`.\n- Now we subtract the `absMin`--->`2*`.why?\n  - First,to remove the `val` we added dureing the entire matrix sum `sum`.\n  - After removing the extra `val` .Secondly,to arrive at the ans(`sum`),we subtract it to give the effect of that negative val.  \n\n# Complexity\n- Time complexity:$O(n*m)$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:$O(1)$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```Python3 []\nclass Solution:\n    def maxMatrixSum(self, matrix: List[List[int]]) -> int:\n        totalsum=0\n        negativecount=0\n        minAbs=float(\'inf\')\n        for row in matrix:\n                for i in row:\n                    totalsum+=abs(i)\n                    if i<0:\n                        negativecount+=1 \n                    minAbs=min(minAbs,abs(i))\n        print(totalsum,minAbs)\n        if negativecount%2!=0:\n            totalsum-=2*minAbs \n        print(totalsum)\n        return totalsum    \n       \n```\n```java []\nclass Solution {\n    public long maxMatrixSum(int[][] matrix) {\n        int negativecount=0;\n        long sum=0;\n        long minAbs=Long.MAX_VALUE;\n        for(int[] row:matrix){\n            for(int i:row){\n                sum+=Math.abs(i);\n                if(i<0)negativecount++;\n                minAbs=Math.min(minAbs,Math.abs(i));\n            }\n        }\n        if(negativecount%2==1)sum-=2*minAbs;\n        return sum;\n    }\n}\n```
['Array', 'Math', 'Greedy', 'Matrix', 'Prefix Sum', 'Java', 'Python3']