Maximum sum in a 2 x n grid such that no two elements are adjacent
Given a rectangular grid of dimension 2 x n. We need to find out the maximum sum such that no two chosen numbers are adjacent, vertically, diagonally, or horizontally.
Examples:
Input: 1 4 5 2 0 0 Output: 7 If we start from 1 then we can add only 5 or 0. So max_sum = 6 in this case. If we select 2 then also we can add only 5 or 0. So max_sum = 7 in this case. If we select from 4 or 0 then there is no further elements can be added. So, Max sum is 7. Input: 1 2 3 4 5 6 7 8 9 10 Output: 24
Approach:
This problem is an extension of Maximum sum such that no two elements are adjacent. The only thing to be changed is to take a maximum element of both rows of a particular column. We traverse column by column and maintain the maximum sum considering two cases.
1) An element of the current column is included. In this case, we take a maximum of two elements in the current column.
2) An element of the current column is excluded (or not included)
Below is the implementation of the above steps.
C++
// C++ program to find maximum sum in a grid such that // no two elements are adjacent. #include<bits/stdc++.h> #define MAX 1000 using namespace std; // Function to find max sum without adjacent int maxSum( int grid[2][MAX], int n) { // Sum including maximum element of first column int incl = max(grid[0][0], grid[1][0]); // Not including first column's element int excl = 0, excl_new; // Traverse for further elements for ( int i = 1; i<n; i++ ) { // Update max_sum on including or excluding // of previous column excl_new = max(excl, incl); // Include current column. Add maximum element // from both row of current column incl = excl + max(grid[0][i], grid[1][i]); // If current column doesn't to be included excl = excl_new; } // Return maximum of excl and incl // As that will be the maximum sum return max(excl, incl); } // Driver code int main() { int grid[2][MAX] = {{ 1, 2, 3, 4, 5}, { 6, 7, 8, 9, 10}}; int n = 5; cout << maxSum(grid, n); return 0; } |
C
// C program to find maximum sum in a grid such that // no two elements are adjacent. #include <stdio.h> #define MAX 1000 // Function to find max sum without adjacent int maxSum( int grid[2][MAX], int n) { // Sum including maximum element of first column int max = grid[0][0]; if (max < grid[1][0]) max = grid[1][0]; int incl = max; // Not including first column's element int excl = 0, excl_new; // Traverse for further elements for ( int i = 1; i<n; i++ ) { // Update max_sum on including or excluding // of previous column max = excl; if (max < incl) max = incl; excl_new = max; // Include current column. Add maximum element // from both row of current column max = grid[0][i]; if (max < grid[1][i]) max = grid[1][i]; incl = excl + max; // If current column doesn't to be included excl = excl_new; } // Return maximum of excl and incl // As that will be the maximum sum max = excl; if (max < incl) max = incl; return max; } // Driver code int main() { int grid[2][MAX] = {{ 1, 2, 3, 4, 5}, { 6, 7, 8, 9, 10}}; int n = 5; printf ( "%d" ,maxSum(grid, n)); return 0; } // This code is contributed by kothavvsaakash. |
Java
// Java Code for Maximum sum in a 2 x n grid // such that no two elements are adjacent import java.util.*; class GFG { // Function to find max sum without adjacent public static int maxSum( int grid[][], int n) { // Sum including maximum element of first // column int incl = Math.max(grid[ 0 ][ 0 ], grid[ 1 ][ 0 ]); // Not including first column's element int excl = 0 , excl_new; // Traverse for further elements for ( int i = 1 ; i < n; i++ ) { // Update max_sum on including or // excluding of previous column excl_new = Math.max(excl, incl); // Include current column. Add maximum element // from both row of current column incl = excl + Math.max(grid[ 0 ][i], grid[ 1 ][i]); // If current column doesn't to be included excl = excl_new; } // Return maximum of excl and incl // As that will be the maximum sum return Math.max(excl, incl); } /* Driver program to test above function */ public static void main(String[] args) { int grid[][] = {{ 1 , 2 , 3 , 4 , 5 }, { 6 , 7 , 8 , 9 , 10 }}; int n = 5 ; System.out.println(maxSum(grid, n)); } } // This code is contributed by Arnav Kr. Mandal. |
Python3
# Python3 program to find maximum sum in a grid such that # no two elements are adjacent. # Function to find max sum without adjacent def maxSum(grid, n) : # Sum including maximum element of first column incl = max (grid[ 0 ][ 0 ], grid[ 1 ][ 0 ]) # Not including first column's element excl = 0 # Traverse for further elements for i in range ( 1 , n) : # Update max_sum on including or excluding # of previous column excl_new = max (excl, incl) # Include current column. Add maximum element # from both row of current column incl = excl + max (grid[ 0 ][i], grid[ 1 ][i]) # If current column doesn't to be included excl = excl_new # Return maximum of excl and incl # As that will be the maximum sum return max (excl, incl) # Driver code if __name__ = = "__main__" : grid = [ [ 1 , 2 , 3 , 4 , 5 ], [ 6 , 7 , 8 , 9 , 10 ] ] n = 5 print (maxSum(grid, n)) / / This code is contributed by Ryuga |
C#
// C# program Code for Maximum sum // in a 2 x n grid such that no two // elements are adjacent using System; class GFG { // Function to find max sum // without adjacent public static int maxSum( int [,]grid, int n) { // Sum including maximum element // of first column int incl = Math.Max(grid[0, 0], grid[1, 0]); // Not including first column's // element int excl = 0, excl_new; // Traverse for further elements for ( int i = 1; i < n; i++ ) { // Update max_sum on including or // excluding of previous column excl_new = Math.Max(excl, incl); // Include current column. Add // maximum element from both // row of current column incl = excl + Math.Max(grid[0, i], grid[1, i]); // If current column doesn't // to be included excl = excl_new; } // Return maximum of excl and incl // As that will be the maximum sum return Math.Max(excl, incl); } // Driver Code public static void Main(String[] args) { int [,]grid = {{ 1, 2, 3, 4, 5}, { 6, 7, 8, 9, 10}}; int n = 5; Console.Write(maxSum(grid, n)); } } // This code is contributed // by PrinciRaj1992 |
PHP
<?php // PHP program to find maximum sum // in a grid such that no two elements // are adjacent. // Function to find max sum // without adjacent function maxSum( $grid , $n ) { // Sum including maximum element // of first column $incl = max( $grid [0][0], $grid [1][0]); // Not including first column's element $excl = 0; $excl_new ; // Traverse for further elements for ( $i = 1; $i < $n ; $i ++ ) { // Update max_sum on including or // excluding of previous column $excl_new = max( $excl , $incl ); // Include current column. Add maximum // element from both row of current column $incl = $excl + max( $grid [0][ $i ], $grid [1][ $i ]); // If current column doesn't // to be included $excl = $excl_new ; } // Return maximum of excl and incl // As that will be the maximum sum return max( $excl , $incl ); } // Driver code $grid = array ( array (1, 2, 3, 4, 5), array (6, 7, 8, 9, 10)); $n = 5; echo maxSum( $grid , $n ); // This code is contributed by Sachin.. ?> |
Javascript
<script> // JavaScript program Code for Maximum sum // in a 2 x n grid such that no two // elements are adjacent // Function to find max sum // without adjacent function maxSum(grid,n) { // Sum including maximum element // of first column let incl = Math.max(grid[0][0], grid[1][0]); // Not including first column's // element let excl = 0, excl_new; // Traverse for further elements for (let i = 1; i < n; i++ ) { // Update max_sum on including or // excluding of previous column excl_new = Math.max(excl, incl); // Include current column. Add // maximum element from both // row of current column incl = excl + Math.max(grid[0][i], grid[1][i]); // If current column doesn't // to be included excl = excl_new; } // Return maximum of excl and incl // As that will be the maximum sum return Math.max(excl, incl); } // Driver Code let grid =[[ 1, 2, 3, 4, 5], [6, 7, 8, 9, 10]]; let n = 5; document.write(maxSum(grid, n)); // This code is contributed // by PrinciRaj1992 </script> |
Output:
24
Time Complexity: O(n) where n is number of elements in given array. As, we are using a loop to traverse N times so it will cost us O(N) time
Auxiliary Space: O(1), as we are not using any extra space.
Contact Us