Given a matrix arr[][] of dimensions 2 * N, the task is to maximize the sum possible by selecting at most one element from each column such that no two consecutive elements are chosen from the same row.
Examples:
Input: arr[][] = {{1, 50, 21, 5}, {2, 10, 10, 5}}
Output: 67
Explanation: Elements arr[1][0]( = 2), arr[0][1]( = 50), arr[0][2]( = 10) and arr[0][3]( = 5) can be chosen. Therefore, sum = 2 + 50 + 10 + 5 = 67.Input: arr[][] = {{9, 5, 3, 7, 3}, {50, 8, 1, 50, 5}}
Output: 108
Explanation: Elements arr[1][0]( = 50), arr[0][1]( = 5), arr[1][3]( = 50) and arr[0][4]( = 3) can be chosen. Therefore, sum = 50 + 5 + 50 + 3 = 108.
Dynamic Programming Approach: The problem can be solved using dynamic programming. Follow the steps below to solve the problem:
- Initialize an array dp[][] to store the following transition states:
dp[0][i] = max(dp[1][i+1], dp[0][i+2]) + arr[0][i]
dp[1][i] = max(dp[0][i+1], dp[1][i+2]) + arr[1][i]
where, dp[j][i] stores the maximum possible sum to reach cell arr[j][i] starting from the last column where 0 <= i < N and 0 <= j < 2.Base case:
dp[0][N-1] = arr[0][N-1]
dp[1][N-1] = arr[1][N-1]
- Traverse from (N – 2)th column to the 0th column and for each row, update dp[j][i] as dp[j][i] = max(dp[(j ^ 1)][i+1], dp[j][i+2]) + arr[j][i] where ^ represents Bitwise XOR.
- After completing the traversal, print max(dp[0][0], dp[1][0]) as the maximum possible sum.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <iostream>#include <vector>using namespace std;// Function to print the maximum sumvoid maxSum(vector<vector<int> > arr, int n, int m){ // Dp table vector<vector<int> > dp(n); // Initializing dp array with 0s for (int i = 0; i < 2; i++) { dp[i] = vector<int>(m); for (int j = 0; j < m; j++) { dp[i][j] = 0; } } // Base case dp[0][m - 1] = arr[0][m - 1]; dp[1][m - 1] = arr[1][m - 1]; // Traverse each column for (int j = m - 2; j >= 0; j--) { // Update answer for both rows for (int i = 0; i < 2; i++) { if (i == 1) { dp[i][j] = max( arr[i][j] + dp[0][j + 1], arr[i][j] + dp[0][j + 2]); } else { dp[i][j] = max( arr[i][j] + dp[1][j + 1], arr[i][j] + dp[1][j + 2]); } } } // Print the maximum sum cout << max(dp[0][0], dp[1][0]);}// Driver Codeint main(){ // Given array vector<vector<int> > arr = { { 1, 50, 21, 5 }, { 2, 10, 10, 5 } }; // Number of Columns int N = arr[0].size(); // Function calls maxSum(arr, 2, N); return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.util.*;class GFG{// Function to print the maximum sumstatic void maxSum(int[][] arr, int n, int m){ // Dp table int[][] dp = new int[n][m + 1]; // Initializing dp array with 0s for(int i = 0; i < 2; i++) { for(int j = 0; j <= m; j++) { dp[i][j] = 0; } } // Base case dp[0][m - 1] = arr[0][m - 1]; dp[1][m - 1] = arr[1][m - 1]; // Traverse each column for(int j = m - 2; j >= 0; j--) { // Update answer for both rows for (int i = 0; i < 2; i++) { if (i == 1) { dp[i][j] = Math.max( arr[i][j] + dp[0][j + 1], arr[i][j] + dp[0][j + 2]); } else { dp[i][j] = Math.max( arr[i][j] + dp[1][j + 1], arr[i][j] + dp[1][j + 2]); } } } // Print the maximum sum System.out.println(Math.max(dp[0][0], dp[1][0]));}// Driver Codepublic static void main(String[] args){ // Given array int[][] arr = { { 1, 50, 21, 5 }, { 2, 10, 10, 5 } }; // Number of Columns int N = arr[0].length; // Function calls maxSum(arr, 2, N);}}// This code is contributed by akhilsaini |
Python3
# Python3 program for the above approach# Function to print the maximum sumdef maxSum(arr, n, m): # Dp table dp = [[0 for i in range(m + 1)] for i in range(2)] # Initializing dp array with 0s # for (i = 0 i < 2 i++) { # dp[i] = vector<int>(m) # for (j = 0 j < m j++) { # dp[i][j] = 0 # } # } # Base case dp[0][m - 1] = arr[0][m - 1] dp[1][m - 1] = arr[1][m - 1] # Traverse each column for j in range(m - 2, -1, -1): # Update answer for both rows for i in range(2): if (i == 1): dp[i][j] = max(arr[i][j] + dp[0][j + 1], arr[i][j] + dp[0][j + 2]) else: dp[i][j] = max(arr[i][j] + dp[1][j + 1], arr[i][j] + dp[1][j + 2]) # Print the maximum sum print(max(dp[0][0], dp[1][0]))# Driver Codeif __name__ == '__main__': # Given array arr = [ [ 1, 50, 21, 5 ], [ 2, 10, 10, 5 ] ] # Number of Columns N = len(arr[0]) # Function calls maxSum(arr, 2, N)# This code is contributed by mohit kumar 29 |
C#
// C# program for the above approachusing System;class GFG{// Function to print the maximum sumstatic void maxSum(int[, ] arr, int n, int m){ // Dp table int[, ] dp = new int[n, m + 1]; // Initializing dp array with 0s for(int i = 0; i < 2; i++) { for(int j = 0; j <= m; j++) { dp[i, j] = 0; } } // Base case dp[0, m - 1] = arr[0, m - 1]; dp[1, m - 1] = arr[1, m - 1]; // Traverse each column for(int j = m - 2; j >= 0; j--) { // Update answer for both rows for(int i = 0; i < 2; i++) { if (i == 1) { dp[i, j] = Math.Max( arr[i, j] + dp[0, j + 1], arr[i, j] + dp[0, j + 2]); } else { dp[i, j] = Math.Max( arr[i, j] + dp[1, j + 1], arr[i, j] + dp[1, j + 2]); } } } // Print the maximum sum Console.WriteLine(Math.Max(dp[0, 0], dp[1, 0]));}// Driver Codepublic static void Main(){ // Given array int[, ] arr = { { 1, 50, 21, 5 }, { 2, 10, 10, 5 } }; // Number of Columns int N = arr.GetLength(1); // Function calls maxSum(arr, 2, N);}}// This code is contributed by akhilsaini |
Javascript
<script>// JavaScript program to implement// the above approach// Function to print the maximum sumfunction maxSum(arr, n, m){ // Dp table let dp = new Array(n); // Loop to create 2D array using 1D array for (var i = 0; i < dp.length; i++) { dp[i] = new Array(2); } // Initializing dp array with 0s for(let i = 0; i < 2; i++) { for(let j = 0; j <= m; j++) { dp[i][j] = 0; } } // Base case dp[0][m - 1] = arr[0][m - 1]; dp[1][m - 1] = arr[1][m - 1]; // Traverse each column for(let j = m - 2; j >= 0; j--) { // Update answer for both rows for (let i = 0; i < 2; i++) { if (i == 1) { dp[i][j] = Math.max( arr[i][j] + dp[0][j + 1], arr[i][j] + dp[0][j + 2]); } else { dp[i][j] = Math.max( arr[i][j] + dp[1][j + 1], arr[i][j] + dp[1][j + 2]); } } } // Print the maximum sum document.write(Math.max(dp[0][0], dp[1][0]));}// Driver Code // Given array let arr = [[ 1, 50, 21, 5 ], [ 2, 10, 10, 5 ]]; // Number of Columns let N = arr[0].length; // Function calls maxSum(arr, 2, N); </script> |
Output:
67
Time Complexity: O(N), where N is the number of columns.
Auxiliary Space: O(N)
Efficient Approach: Follow the steps below to optimize the above approach
- Initialize two variables r1 and r2 to store the maximum sum for 1st and 2nd rows respectively.
- Traverse over the length of the row, i.e. 0 to N – 1 and for each element arr[i], update r1 as r1 = max(r1, r2 + arr[0][i]) and r2 as r2 = max(r2, r1 + arr[1][i]).
- After traversing, print max(r1, r2) as the maximum sum.
Below is the implementation of the above approach:
C++
// C++ code for the above approach#include <bits/stdc++.h>using namespace std;// Function to print the maximum sum// possible by selecting at most one// element from each column such that// no consecutive pairs are selected// from a single rowvoid maxSum(vector<vector<int> > arr, int n){ // Initialize variables int r1 = 0, r2 = 0; // Traverse each column for(int i = 0; i < n; i++) { // r1, r2 = max(r1, r2 + arr[0][i]), // max(r2, r1 + arr[1][i]) int temp = r1; r1 = max(r1, r2 + arr[0][i]); r2 = max(r2, temp + arr[1][i]); } // Print answer cout << max(r1, r2);}// Driver Codeint main(){ vector<vector<int>> arr = { { 1, 50, 21, 5 }, { 2, 10, 10, 5 } }; // Numberof columns int n = arr[0].size(); maxSum(arr, n); return 0;}// This code is contributed by akhilsaini |
Java
// Java code for the above approachimport java.io.*;import java.util.*;class GFG{// Function to print the maximum sum// possible by selecting at most one// element from each column such that// no consecutive pairs are selected// from a single rowstatic void maxSum(int[][] arr, int n){ // Initialize variables int r1 = 0, r2 = 0; // Traverse each column for(int i = 0; i < n; i++) { int temp = r1; r1 = Math.max(r1, r2 + arr[0][i]); r2 = Math.max(r2, temp + arr[1][i]); } // Print answer System.out.println(Math.max(r1, r2));}// Driver Codepublic static void main(String args[]){ int[][] arr = { { 1, 50, 21, 5 }, { 2, 10, 10, 5 } }; // Numberof columns int n = arr[0].length; maxSum(arr, n);}}// This code is contributed by akhilsaini |
Python
# Python code for the above approach# Function to print the maximum sum# possible by selecting at most one# element from each column such that# no consecutive pairs are selected# from a single rowdef maxSum(arr, n): # Initialize variables r1 = r2 = 0 # Traverse each column for i in range(n): r1, r2 = max(r1, r2 + arr[0][i]), max(r2, r1 + arr[1][i]) # Print answer print(max(r1, r2))# Driver Codearr = [[1, 50, 21, 5], [2, 10, 10, 5]]# Numberof columnsn = len(arr[0])maxSum(arr, n) |
C#
// C# code for the above approachusing System;class GFG{// Function to print the maximum sum// possible by selecting at most one// element from each column such that// no consecutive pairs are selected// from a single rowstatic void maxSum(int[, ] arr, int n){ // Initialize variables int r1 = 0, r2 = 0; // Traverse each column for(int i = 0; i < n; i++) { int temp = r1; r1 = Math.Max(r1, r2 + arr[0, i]); r2 = Math.Max(r2, temp + arr[1, i]); } // Print answer Console.WriteLine(Math.Max(r1, r2));}// Driver Codepublic static void Main(){ int[, ] arr = { { 1, 50, 21, 5 }, { 2, 10, 10, 5 } }; // Numberof columns int n = arr.GetLength(1); maxSum(arr, n);}}// This code is contributed by akhilsaini |
Javascript
<script>// Javascript code for the above approach // Function to print the maximum sum // possible by selecting at most one // element from each column such that // no consecutive pairs are selected // from a single row function maxSum(arr , n) { // Initialize variables var r1 = 0, r2 = 0; // Traverse each column for (i = 0; i < n; i++) { var temp = r1; r1 = Math.max(r1, r2 + arr[0][i]); r2 = Math.max(r2, temp + arr[1][i]); } // Print answer document.write(Math.max(r1, r2)); } // Driver Code var arr = [ [ 1, 50, 21, 5 ], [ 2, 10, 10, 5 ] ]; // Numberof columns var n = arr[0].length; maxSum(arr, n);// This code is contributed by todaysgaurav</script> |
Output:
67
Time Complexity: O(N), where N is the number of columns.
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
