Maximize sum by selecting contiguous elements from each row or column
Given a matrix mat[][] of size M x N where mat[i][j], the task is to find the maximum possible sum by picking contiguous elements from each or from each column.
Note: It is compulsory to pick at least one element from each row or column and you can perform this either in rows only or in columns only.
Examples:
Input: mat[][] = [ [-3, 0, -5, -8], [4, -3, 4, -2], [4, 3, -8, 6], [-1, -1, -1, -1] ]
Output: 21
Explanation: Max amount if moving horizontally = 0(1st row) + 4 – 3 + 4 (2nd row) + 4 + 3 (3rd row) – 1 (4th row) = 0 + 5 + 7 – 1 = 11
Max amount if moving vertically = 4+4 (1st column) + 3 (2nd row) + 4 (3rd row) + 6 (4th row) = 8 + 3 + 4 + 6 = 21
Maximum sum = max(11, 21) = 21Input: mat = [ [-1, -2], [-1, -3] ]
Output: -2
Approach: The problem can be solved using Kadane’s Algorithm based on the following idea:
- Store the maximum contiguous sum for each row in a variable row sum
- Store the maximum contiguous sum for each column in a variable col sum
If selecting elements only from row then the sum of row sums will be the maximum sum and if selecting columns only then the sum of columns will be the maximum column. The maximum among these two sums is the required answer.
Follow the steps mentioned below to implement the idea:
- Traverse matrix mat[][] first of all row-wise and store each row in a vector and
- Find the maximum sum using Kadane’s algorithm described above.
- Add the maximum sum for each row in a variable rowsum.
- Similarly, traverse matrix mat[][] column-wise and store each column in a vector and
- Find the maximum sum using Kadane’s algorithm described above.
- Add the maximum sum for each column in a variable colsum.
- Maximum out of rowsum and colsum will be the maximum possible sum traversing it either horizontally or vertically.
Below is the implementation of the above approach.
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Function for calculating maximum // contiguous sum int max_contiguous_sum(vector< int >& arr) { int curr_sum = 0; int max_sum = INT_MIN; for ( int i = 0; i < arr.size(); i++) { // Adding current amount to // the curr_sum curr_sum += arr[i]; // If at any point current sum // become greater than the maximum // sum, update maximum sum if (curr_sum > max_sum) { max_sum = curr_sum; } // If current sum becomes negative, // skip and do a fresh start if (curr_sum < 0) { curr_sum = 0; } } // Returning maximum sum return max_sum; } // Function to find the maximum possible sum int maxSum(vector<vector< int > >& mat, int m, int n) { // Store all row sum int row_sum = 0; // Store all col sum int col_sum = 0; for ( int i = 0; i < m; i++) { // Store 1 row everytime vector< int > temp; for ( int j = 0; j < n; j++) { temp.push_back(mat[i][j]); } // Adding all row sum turn by turn row_sum += max_contiguous_sum(temp); } for ( int i = 0; i < m; i++) { // Store 1 col everytime vector< int > temp; for ( int j = 0; j < n; j++) { temp.push_back(mat[j][i]); } // Adding all col sum turn by turn col_sum += max_contiguous_sum(temp); } // Taking maximum of col sum // and row sum int ans = max(row_sum, col_sum); return ans; } // Driver code int main() { vector<vector< int > > mat = { { -3, 0, -5 - 8 }, { 4, -3, 4, -2 }, { 4, 3, -8, 6 }, { -1, -1, -1, -1 } }; int M = mat.size(); int N = mat[0].size(); // Function call int ans = maxSum(mat, M, N); cout << ans << endl; return 0; } |
Java
// Java code to implement the approach import java.util.*; public class GFG { // Function for calculating maximum // contiguous sum static int max_contiguous_sum(ArrayList<Integer> arr) { int curr_sum = 0 ; int max_sum = Integer.MIN_VALUE; for ( int i = 0 ; i < arr.size(); i++) { // Adding current amount to // the curr_sum curr_sum += arr.get(i); // If at any point current sum // become greater than the maximum // sum, update maximum sum if (curr_sum > max_sum) { max_sum = curr_sum; } // If current sum becomes negative, // skip and do a fresh start if (curr_sum < 0 ) { curr_sum = 0 ; } } // Returning maximum sum return max_sum; } // Function to find the maximum possible sum static int maxSum( int [][] mat, int m, int n) { // Store all row sum int row_sum = 0 ; // Store all col sum int col_sum = 0 ; for ( int i = 0 ; i < m; i++) { // Store 1 row everytime ArrayList<Integer> temp = new ArrayList<Integer>(); for ( int j = 0 ; j < n; j++) { temp.add(mat[i][j]); } // Adding all row sum turn by turn row_sum += max_contiguous_sum(temp); } for ( int i = 0 ; i < m; i++) { // Store 1 col everytime ArrayList<Integer> temp = new ArrayList<Integer>(); for ( int j = 0 ; j < n; j++) { temp.add(mat[j][i]); } // Adding all col sum turn by turn col_sum += max_contiguous_sum(temp); } // Taking maximum of col sum // and row sum int ans = Math.max(row_sum, col_sum); return ans; } // Driver code public static void main(String[] args) { int [][] mat = { { - 3 , 0 , - 5 , - 8 }, { 4 , - 3 , 4 , - 2 }, { 4 , 3 , - 8 , 6 }, { - 1 , - 1 , - 1 , - 1 } }; int M = 4 ; int N = 4 ; // Function call int ans = maxSum(mat, M, N); System.out.println(ans); } } // This code is contributed by garg28harsh. |
Python3
# Python3 code to implement the approach # Function for calculating maximum # contiguous sum def max_contiguous_sum(arr): curr_sum = 0 max_sum = - 2147483647 - 1 for i in range ( 0 , len (arr)): # Adding current amount to # the curr_sum curr_sum + = arr[i] # If at any point current sum # become greater than the maximum # sum, update maximum sum if (curr_sum > max_sum): max_sum = curr_sum # If current sum becomes negative, # skip and do a fresh start if (curr_sum < 0 ): curr_sum = 0 # Returning maximum sum return max_sum # Function to find the maximum possible sum def maxSum(mat, m, n): # Store all row sum row_sum = 0 # Store all col sum col_sum = 0 for i in range ( 0 ,m): # Store 1 row everytime temp = [] for j in range ( 0 ,n): temp.append(mat[i][j]) # Adding all row sum turn by turn row_sum + = max_contiguous_sum(temp) for i in range ( 0 , 4 ): # Store 1 col everytime temp = [] for j in range ( 0 , 3 ): temp.append(mat[j][i]) # Adding all col sum turn by turn col_sum + = max_contiguous_sum(temp) # Taking maximum of col sum # and row sum ans = max (row_sum, col_sum) return ans # Driver code mat = [ [ - 3 , 0 , - 5 , - 8 ], [ 4 , - 3 , 4 , - 2 ], [ 4 , 3 , - 8 , 6 ], [ - 1 , - 1 , - 1 , - 1 ] ] M = len (mat) N = len (mat[ 0 ]) # Function call ans = maxSum(mat, M, N) print (ans) # This code is contributed by akashish__ |
C#
// C# implementation using System; public class GFG { // Function for calculating maximum // contiguous sum static int max_contiguous_sum( int [] arr) { int curr_sum = 0; int max_sum = int .MinValue; for ( int i = 0; i < arr.Length; i++) { // Adding current amount to // the curr_sum curr_sum += arr[i]; // If at any point current sum // become greater than the maximum // sum, update maximum sum if (curr_sum > max_sum) { max_sum = curr_sum; } // If current sum becomes negative, // skip and do a fresh start if (curr_sum < 0) { curr_sum = 0; } } // Returning maximum sum return max_sum; } // Function to find the maximum possible sum static int maxSum( int [, ] mat, int m, int n) { // Store all row sum int row_sum = 0; // Store all col sum int col_sum = 0; for ( int i = 0; i < m; i++) { // Store 1 row everytime int [] temp = new int [n]; for ( int j = 0; j < n; j++) { temp[j] = (mat[i, j]); } // Adding all row sum turn by turn row_sum += max_contiguous_sum(temp); } for ( int i = 0; i < m; i++) { // Store 1 col everytime int [] temp = new int [n]; for ( int j = 0; j < n; j++) { temp[j] = (mat[j, i]); } // Adding all col sum turn by turn col_sum += max_contiguous_sum(temp); } // Taking maximum of col sum // and row sum int ans = Math.Max(row_sum, col_sum); return ans; } static public void Main() { int [, ] mat = { { -3, 0, -5, -8 }, { 4, -3, 4, -2 }, { 4, 3, -8, 6 }, { -1, -1, -1, -1 } }; int M = mat.GetLength(0); int N = mat.GetLength(1); // Function call int ans = maxSum(mat, M, N); Console.WriteLine(ans); } } // this code is contributed by ksam24000 |
Javascript
// Javascript code to implement the approach // Function for calculating maximum // contiguous sum function max_contiguous_sum( arr) { let curr_sum = 0; let max_sum = Number.MIN_VALUE; for (let i = 0; i < arr.length; i++) { // Adding current amount to // the curr_sum curr_sum += arr[i]; // If at any point current sum // become greater than the maximum // sum, update maximum sum if (curr_sum > max_sum) { max_sum = curr_sum; } // If current sum becomes negative, // skip and do a fresh start if (curr_sum < 0) { curr_sum = 0; } } // Returning maximum sum return max_sum; } // Function to find the maximum possible sum function maxSum(mat, m, n) { // Store all row sum let row_sum = 0; // Store all col sum let col_sum = 0; for (let i = 0; i < m; i++) { // Store 1 row everytime let temp = []; for (let j = 0; j < n; j++) { temp.push(mat[i][j]); } // Adding all row sum turn by turn row_sum += max_contiguous_sum(temp); } for (let i = 0; i < m; i++) { // Store 1 col everytime temp = []; for (let j = 0; j < n; j++) { temp.push(mat[j][i]); } // Adding all col sum turn by turn col_sum += max_contiguous_sum(temp); } // Taking maximum of col sum // and row sum let ans = Math.max(row_sum, col_sum); return ans; } // Driver code let mat = [ [ -3, 0, -5, - 8 ],[ 4, -3, 4, -2 ], [ 4, 3, -8, 6 ],[ -1, -1, -1, -1 ] ]; let M = mat.length; let N = mat[0].length; // Function call let ans = maxSum(mat, M, N); console.log(ans); // This code is contributed by akashish__. |
21
Time Complexity: O(M * N)
Space Complexity: O(max(M, N))
Contact Us