You are given an n x n integer matrix. You can do the following operation any number of times:
- Choose any two adjacent elements of
matrixand multiply each of them by-1.
Two elements are considered adjacent if and only if they share a border.
Your goal is to maximize the summation of the matrix’s elements. Return the maximum sum of the matrix’s elements using the operation mentioned above.
Example 1:
Input: matrix = [[1,-1],[-1,1]] Output: 4 Explanation: We can follow the following steps to reach sum equals 4: - Multiply the 2 elements in the first row by -1. - Multiply the 2 elements in the first column by -1.
Example 2:
Input: matrix = [[1,2,3],[-1,-2,-3],[1,2,3]] Output: 16 Explanation: We can follow the following step to reach sum equals 16: - Multiply the 2 last elements in the second row by -1.
Constraints:
n == matrix.length == matrix[i].length2 <= n <= 250-105 <= matrix[i][j] <= 105
Solution: Math
Count the number of negative numbers.
1. Even negatives, we can always flip all the negatives to positives. ans = sum(abs(matrix)).
2. Odd negatives, there will be one negative left, we found the smallest abs(element) and let it become negative. ans = sum(abs(matrix))) – 2 * min(abs(matrix))
Time complexity: O(n2)
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
// Author: Huahua class Solution { public: long long maxMatrixSum(vector<vector<int>>& matrix) { const int n = matrix.size(); long long ans = 0; int count = 0; int lo = INT_MAX; for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) { ans += abs(matrix[i][j]); lo = min(lo, abs(matrix[i][j])); count += matrix[i][j] < 0; } return ans - (count & 1) * 2 * lo; } }; |