(Rust | Typescript) Easy Solution Beats 100% EXPLAINED ✅ | Greedy Intuition
\n\n# Intuition\nFrom the problem statement and given examples, we can conclude an intuition that every matrix element can be made positive if the number of neg
![image.png](https://assets.leetcode.com/users/images/92d3155c-1d12-4f8a-9dd7-bdefc73b8247_1732428917.5406718.png)\n\n# Intuition\nFrom the problem statement and given examples, we can conclude an intuition that every matrix element can be made positive if the number of negative elements in the initial matrix is even. If it\'s odd, then we can make the smallest element negative to maximize the sum.\n\n# Approach\nFirst we initialize 3 variables, `sum`(for storing the sum of elements of the matrix), `min`(for storing the smallest element), and `neg_count`(for storing the frequency of negative elements).\n\nNavigate through the matrix. Each time we go through an element,\n- We add its absolute value to `sum`.\n- Increment `neg_count` if it\'s a negative number.\n- And update `min` if it\'s smaller than min.\n\nAfter traversing the matrix:\n- We check if `neg_count` is even, if yes then just return sum without adding anything.\n- If `neg_count` is odd, then we subtract 2 times the minimum value from the sum, and return the resultant value.\n\nBoom! We solved the problem!\n\n# Complexity\n- Time complexity: $$O(n^2)$$\nAs we\'re traversing through each element.\n\n- Space complexity: $$O(1)$$\nSince we\'re not utilizing any additional space.\n\n![Upvote Me Please!](https://assets.leetcode.com/users/images/51cb4fd2-7cb6-43dc-8abe-06258e7f88bc_1731764541.0245967.png)\n\n# Code\n```rust []\nuse std::f64::INFINITY;\n\nimpl Solution {\n    pub fn max_matrix_sum(matrix: Vec<Vec<i32>>) -> i64 {\n        let mut sum = 0 as i64;\n        let mut min = INFINITY as i64;\n        let mut neg_count = 0;\n\n        for row in matrix {\n            for elem in row {\n                sum += elem.abs() as i64;\n                if elem < 0 { neg_count += 1 }\n                min = *[elem.abs() as i64, min].iter().min().unwrap();\n            }\n        }\n\n        sum + {if neg_count%2 == 0 { 0 as i64 } else { -2 * min }}\n    }\n}\n```\n```typescript []\nfunction maxMatrixSum(matrix: number[][]): number {\n    let min = Infinity;\n    let negCount = 0;\n    let sum = 0;\n    \n    matrix.forEach((row) =>\n        row.forEach((elem) => {\n            min = Math.min(Math.abs(elem), min);\n            if(elem < 0) negCount += 1;\n            sum += Math.abs(elem)\n        })\n    );\n\n    return sum + (negCount%2===0?0:-2*min)\n};\n```
['Array', 'Greedy', 'Matrix', 'TypeScript', 'Rust', 'JavaScript']