我是偉大的矩陣

1975 年。最大矩陣和

難度：中

主題：陣列、貪婪、矩陣

給你一個 n x n 整數矩陣。您可以執行以下操作：

• 選取矩陣中任兩個相鄰元素，然後將每個元素乘以-1。

兩個元素被視為相鄰當且僅當它們共用邊框。

您的目標是最大化矩陣元素的總和。使用上述運算傳回矩陣元素的最大總和。

範例1：

• 輸入： 矩陣 = [[1,-1],[-1,1]]
• 輸出： 4
• 解釋：我們可以依照以下步驟讓總和等於 4：
  • 將第一行的 2 個元素乘以 -1。
  • 將第一列的 2 個元素乘以 -1。

範例2：

• 輸入： 矩陣 = [[1,2,3],[-1,-2,-3],[1,2,3]]
• 輸出： 16
• 解釋：我們可以依照以下步驟讓總和等於 16：
  • 將第二行的最後 2 個元素乘以 -1。

約束：

• n == 矩陣.length == 矩陣[i].length
• 2
• -10⁵ 5

提示：

1. 嘗試使用運算使每一行只有一個負數。
2. 如果只有一個負元素，則無法將其轉換為正元素。

解：

為了使用該運算最大化矩陣的總和，我們需要最小化總和的負貢獻的絕對值。計劃如下：

1. 計算負數：追蹤矩陣中存在多少個負數。
2. 找出最小絕對值：確定矩陣中的最小絕對值，如果負數為奇數，這將有幫助。
3. 調整奇數負數：如果負數的數量是奇數，則最小絕對值無法翻轉為正數，這限制了最大可能的總和。

讓我們用 PHP 實作這個解：1975。最大矩陣和

<?php
/**
 * @param Integer[][] $matrix
 * @return Integer
 */
function maximumMatrixSum($matrix) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test case 1
$matrix1 = [[1, -1], [-1, 1]];
echo "Output: " . maximumMatrixSum($matrix1) . "\n"; // Output: 4

// Test case 2
$matrix2 = [[1, 2, 3], [-1, -2, -3], [1, 2, 3]];
echo "Output: " . maximumMatrixSum($matrix2) . "\n"; // Output: 16
?>

解釋：

1. 絕對值求和： 計算所有元素的絕對值總和，因為最佳配置將盡可能多的負數翻轉為正數。
2. 追蹤最小絕對值：當負數計數為奇數時，使用此功能調整總和。
3. 處理奇負數：當負數無法完全抵消時，從總和中減去最小絕對值的兩倍，以考慮不可避免的負數。

複雜

• 時間複雜度： O(n^2)，因為矩陣被遍歷一次。
• 空間複雜度： O(1)，因為除了變數之外沒有使用額外的空間。

該解決方案在給定的限制內有效地工作。

聯絡連結

如果您發現本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub

以上是我是偉大的矩陣的詳細內容。更多資訊請關注PHP中文網其他相關文章！