# Maximum difference of sum of elements in two rows in a matrix

Given a matrix of m*n order, the task is to find the maximum difference between two rows Rj and Ri such that i < j, i.e., we need to find maximum value of sum(Rj) – sum(Ri) such that row i is above row j.

**Examples:**

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

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

A **simple solution** for this problem is to one by one select each row, compute sum of elements in it and take difference from sum of next rows in forward direction. Finally return the maximum difference. Time complexity for this approach will be O(n*m^{2}).

An **efficient solution** solution for this problem is to first calculate the sum of all elements of each row and store them in an auxiliary array **rowSum[]** and then calculate maximum difference of two elements **max(rowSum[j] – rowSum[i])** such that rowSum[i] < rowSum[j] in linear time. See this article. In this method, we need to keep track of 2 things:

1) Maximum difference found so far (max_diff).

2) Minimum number visited so far (min_element).

## C++

`// 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;` `}` |

## Java

`// Java program to find maximum difference` `// of sum of elements of two rows` `class` `GFG {` `static` `final` `int` `MAX = ` `100` `;` `// Function to find maximum difference of sum` `// of elements of two rows such that second` `// row appears before first row.` `static` `int` `maxRowDiff(` `int` `mat[][], ` `int` `m, ` `int` `n) {` ` ` `// auxiliary array to store sum` ` ` `// of all elements of each row` ` ` `int` `rowSum[] = ` `new` `int` `[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 code` `public` `static` `void` `main(String[] args) {` ` ` `int` `m = ` `5` `, n = ` `4` `;` ` ` `int` `mat[][] = {{-` `1` `, ` `2` `, ` `3` `, ` `4` `},` ` ` `{` `5` `, ` `3` `, -` `2` `, ` `1` `},` ` ` `{` `6` `, ` `7` `, ` `2` `, -` `3` `},` ` ` `{` `2` `, ` `9` `, ` `1` `, ` `4` `},` ` ` `{` `2` `, ` `1` `, -` `2` `, ` `0` `}};` ` ` `System.out.print(maxRowDiff(mat, m, n));` `}` `}` `// This code is contributed by Anant Agarwal.` |

## Python3

`# Python3 program to find maximum difference` `# of sum of elements of two rows` `# Function to find maximum difference of` `# sum of elements of two rows such that` `# second row appears before first row.` `def` `maxRowDiff(mat, m, n):` ` ` ` ` `# auxiliary array to store sum of` ` ` `# all elements of each row` ` ` `rowSum ` `=` `[` `0` `] ` `*` `m` ` ` ` ` `# calculate sum of each row and` ` ` `# store it in rowSum array` ` ` `for` `i ` `in` `range` `(` `0` `, m):` ` ` `sum` `=` `0` ` ` `for` `j ` `in` `range` `(` `0` `, n):` ` ` `sum` `+` `=` `mat[i][j]` ` ` `rowSum[i] ` `=` `sum` ` ` ` ` `# calculating maximum difference of` ` ` `# two elements such that` ` ` `# rowSum[i]<rowsum[j]` ` ` `max_diff ` `=` `rowSum[` `1` `] ` `-` `rowSum[` `0` `]` ` ` `min_element ` `=` `rowSum[` `0` `]` ` ` ` ` `for` `i ` `in` `range` `(` `1` `, m):` ` ` ` ` `# 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` `m ` `=` `5` `n ` `=` `4` `mat ` `=` `[[` `-` `1` `, ` `2` `, ` `3` `, ` `4` `],` ` ` `[` `5` `, ` `3` `, ` `-` `2` `, ` `1` `],` ` ` `[` `6` `, ` `7` `, ` `2` `, ` `-` `3` `],` ` ` `[` `2` `, ` `9` `, ` `1` `, ` `4` `],` ` ` `[` `2` `, ` `1` `, ` `-` `2` `, ` `0` `]]` `print` `( maxRowDiff(mat, m, n))` `# This code is contributed by Swetank Modi` |

## C#

`// C# program to find maximum difference` `// of sum of elements of two rows` `using` `System;` `class` `GFG {` ` ` ` ` `// Function to find maximum difference` ` ` `// of sum of elements of two rows such` ` ` `// that second row appears before` ` ` `// first row.` ` ` `static` `int` `maxRowDiff(` `int` `[,] mat,` ` ` `int` `m, ` `int` `n)` ` ` `{` ` ` ` ` `// auxiliary array to store sum` ` ` `// of all elements of each row` ` ` `int` `[] rowSum = ` `new` `int` `[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 code` ` ` `public` `static` `void` `Main()` ` ` `{` ` ` `int` `m = 5, n = 4;` ` ` `int` `[,] mat = { {-1, 2, 3, 4 },` ` ` `{5, 3, -2, 1 },` ` ` `{6, 7, 2, -3},` ` ` `{2, 9, 1, 4 },` ` ` `{2, 1, -2, 0} };` ` ` ` ` `Console.Write(maxRowDiff(mat, m, n));` ` ` `}` `}` `// This code is contributed by KRV.` |

## PHP

`<?php` `// PHP program to find maximum` `// difference of sum of` `// elements of two rows` `$MAX` `= 100;` `// Function to find maximum` `// difference of sum of` `// elements of two rows such` `// that second row appears` `// before first row.` `function` `maxRowDiff(` `$mat` `, ` `$m` `, ` `$n` `)` `{` ` ` `global` `$MAX` `;` ` ` `// auxiliary array to store` ` ` `// sum of all elements` ` ` `// of each row` ` ` `$rowSum` `= ` `array` `();` ` ` `// calculate sum of each` ` ` `// row and store it in` ` ` `// rowSum array` ` ` `for` `(` `$i` `= 0; ` `$i` `< ` `$m` `; ` `$i` `++)` ` ` `{` ` ` `$sum` `= 0;` ` ` `for` `(` `$j` `= 0; ` `$j` `< ` `$n` `; ` `$j` `++)` ` ` `$sum` `+= ` `$mat` `[` `$i` `][` `$j` `];` ` ` `$rowSum` `[` `$i` `] = ` `$sum` `;` ` ` `}` ` ` `// calculating maximum` ` ` `// difference of two` ` ` `// elements such that` ` ` `// rowSum[i]<rowsum[j]` ` ` `$max_diff` `= ` `$rowSum` `[1] - ` `$rowSum` `[0];` ` ` `$min_element` `= ` `$rowSum` `[0];` ` ` `for` `(` `$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 Code` `$m` `= 5;` `$n` `= 4;` `$mat` `= ` `array` `(` `array` `(-1, 2, 3, 4),` ` ` `array` `(5, 3, -2, 1),` ` ` `array` `(6, 7, 2, -3),` ` ` `array` `(2, 9, 1, 4),` ` ` `array` `(2, 1, -2, 0));` `echo` `maxRowDiff(` `$mat` `, ` `$m` `, ` `$n` `);` `// This code is contributed by ajit` `?>` |

## Javascript

`<script>` `// Javascript program to find maximum difference` `// of sum of elements of two rows` `// Function to find maximum difference` `// of sum of elements of two rows such` `// that second row appears before` `// first row.` `function` `maxRowDiff(mat, m, n)` `{` ` ` ` ` `// Auxiliary array to store sum` ` ` `// of all elements of each row` ` ` `let rowSum = ` `new` `Array(m);` ` ` ` ` `// Calculate sum of each row and` ` ` `// store it in rowSum array` ` ` `for` `(let i = 0; i < m; i++)` ` ` `{` ` ` `let sum = 0;` ` ` ` ` `for` `(let j = 0; j < n; j++)` ` ` `sum += mat[i][j];` ` ` ` ` `rowSum[i] = sum;` ` ` `}` ` ` ` ` `// Calculating maximum difference` ` ` `// of two elements such that` ` ` `// rowSum[i] < rowsum[j]` ` ` `let max_diff = rowSum[1] - rowSum[0];` ` ` `let min_element = rowSum[0];` ` ` ` ` `for` `(let 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 code` `let m = 5, n = 4;` `let mat = [ [ -1, 2, 3, 4 ],` ` ` `[ 5, 3, -2, 1 ],` ` ` `[ 6, 7, 2, -3 ],` ` ` `[ 2, 9, 1, 4 ],` ` ` `[ 2, 1, -2, 0 ] ];` `document.write(maxRowDiff(mat, m, n));` `// This code is contributed by divyesh072019 ` `</script>` |

**Output:**

9

**Time complexity :** O(m*n) **Auxiliary space : **O(m)

This article is contributed by **Shashank Mishra ( Gullu )**. If you like GeeksforGeeks and would like to contribute, you can also write an article using contribute.geeksforgeeks.org or mail your article to contribute@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.