題目

2024/11/24 的每日一題

• https://leetcode.com/problems/maximum-matrix-sum/description
• https://leetcode.cn/problems/maximum-matrix-sum/description （中文）

資料結構與演算法

• 矩陣
• 貪婪
• 數學

題意

可以挑任意兩個數字都乘以 -1 ，已達到整個矩陣所有元素的和為最大值

意味著

1. 負數能變正數，正數能為負數
2. Greedy - 可以先加總所有元素值的絕對值作為總和
   • 當負數為 偶數 個時，透過無限次數的 -1 轉換，能夠都轉為正數，這時候就可以直接回傳
   • 當負數為 奇數 個時，一定會有一個負數會落單，這時候我們會希望落單的負數是最大，換言之是絕對值最 小 的負數。因為當絕對值越大，越能貢獻總和成為更大的數。
     • 接著回傳的總和必須扣掉這個數兩次，一次是 扣掉絕對值 ，一次是 加上負數值
3. 挑負數值
   • 當負數值只剩下一個的時後，必須要考慮像是這樣的 case ，當最小正數比負數的絕對值還要小
     • 最小正數 1, 負數 -3
     • 因為負數變成絕對值後能貢獻的值比較大，這時候就可以呼應 1. 把最小正數轉換乘負數 -1 ，令其成為「落單的負數」。

Routine

解析完題意後，就可以來制定 routine 該做什麼事。這題的 routine 就只有一件事情： 走訪矩陣的每個元素 。

走訪矩陣

走訪矩陣需要先準備這幾個變數：

• 總和
• 最小絕對值
• 負數的個數

走訪過程

1. 把元素的絕對值加到 總和
2. 為了「落單的負數」比較和更新 最小絕對值
3. 當前元素為負值時，進行 負數的個數 += 1

後處理

1. 當負數個數為 偶數 → 回傳 總和 不做其他運算
2. 當負數個數為 奇數 → 把多加了的 最小絕對值 從 總和 扣掉一次後，再加上負值的 最小絕對值。

程式碼

class Solution {
    func maxMatrixSum(_ matrix: [[Int]]) -> Int {
        var sum = 0
        var minimum = Int.max
        var negativeCount = 0

        for row in matrix {
            for column in row {
                sum += abs(column)
                minimum = min(minimum, abs(column))

                if column < 0 {
                    negativeCount += 1
                }
            }
        }

        guard negativeCount % 2 != 0 else {
            return sum
        }

        // sum - absolute min + the negative min
        return sum - minimum - minimum
    }
}

複雜度分析

依題目，陣列大小為 n x n

• 時間複雜度： O(nxn) 或 O(n^2)
  • 線性走訪矩陣，元素個數為 n x n
• 空間複雜度： O(1)
  • 雖然宣告了三個變數為 O(3) ，但是表示時可寫成 O(1)

結語

以上，如果有什麼回饋，歡迎在留言區跟我說，謝謝！