矩陣中兩行元素之和的最大差 · GeeksForGeeks 中文系列教程

# 矩陣中兩行元素之和的最大差 > 原文： [https://www.geeksforgeeks.org/maximum-difference-sum-elements-two-rows-matrix/](https://www.geeksforgeeks.org/maximum-difference-sum-elements-two-rows-matrix/) 給定一個 m * n 階矩陣，任務是找到兩行 Rj 和 Ri 之間的最大差，使得 i < j，即，我們需要找到 sum（Rj）– sum（Ri）的最大值該行 i 在第 j 行上方。 **示例**： ``` Input : mat[5][4] = {{-1, 2, 3, 4}, {5, 3, -2, 1}, {6, 7, 2, -3}, {2, 9, 1, 4}, {2, 1, -2, 0}} Output: 9 // difference of R3 - R1 is maximum ``` 針對此問題的**簡單解決方案**是逐行選擇每一行，計算其中的元素總和，并從正方向上與下一行的總和取差。最后返回最大差。該方法的時間復雜度將為 O（n * m <sup>2</sup> ）。針對此問題的**有效解決方案**解決方案是，首先計算每行所有元素的總和，并將它們存儲在輔助數組 **rowSum []** 中，然后計算兩個元素的最大差 **max（rowSum [j] – rowSum [i]）**使得 rowSum [i] < rowSum [j]在線性時間內。請參閱[此](https://www.geeksforgeeks.org/maximum-difference-between-two-elements/)文章。在此方法中，我們需要跟蹤 2 件事情： 1）到目前為止找到的最大差異（max_diff）。 2）到目前為止訪問的最小人數（min_element）。 ## C++ ```cpp // C++ program to find maximum difference of sum of // elements of two rows #include<bits/stdc++.h> #define MAX 100 using namespace std; // Function to find maximum difference of sum of // elements of two rows such that second row appears // before first row. int maxRowDiff(int mat[][MAX], int m, int n) { ????// auxiliary array to store sum of all elements ????// of each row ????int rowSum[m]; ????// calculate sum of each row and store it in ????// rowSum array ????for (int i=0; i<m; i++) ????{ ????????int sum = 0; ????????for (int j=0; j<n; j++) ????????????sum += mat[i][j]; ????????rowSum[i] = sum; ????} ????// calculating maximum difference of two elements ????// such that rowSum[i]<rowsum[j] ????int max_diff = rowSum[1] - rowSum[0]; ????int min_element = rowSum[0]; ????for (int i=1; i<m; i++) ????{ ????????// if current difference is greater than ????????// previous then update it ????????if (rowSum[i] - min_element > max_diff) ????????????max_diff = rowSum[i] - min_element; ????????// if new element is less than previous minimum ????????// element then update it so that ????????// we may get maximum difference in remaining array ????????if (rowSum[i] < min_element) ????????????min_element = rowSum[i]; ????} ????return max_diff; } // Driver program to run the case int main() { ????int m = 5, n = 4; ????int mat[][MAX] = {{-1, 2, 3, 4}, ?????????????????????{5, 3, -2, 1}, ?????????????????????{6, 7, 2, -3}, ?????????????????????{2, 9, 1, 4}, ?????????????????????{2, 1, -2, 0}}; ????cout << maxRowDiff(mat, m, n); ????return 0; } ```