Given a 2-D array of size N*M where, 
. The task is to find the maximum value achievable by a + shaped pattern. The elements of the array can be negative.
The plus(+) shape pattern is formed by taking any element with co-ordinate (x, y) as a center and then expanding it in all four directions(if possible).
A plus(+) shape has atleast five elements which are { (x-1, y), (x, y-1), (x, y), (x+1, y), (x, y+1) } i.e. the arms should have length>1 but not necessarily need to have same length.
Examples:
Input: N = 3, M = 4
1 1 1 1
-6 1 1 -4
1 1 1 1
Output: 0
Here, (x, y)=(2, 3) center of pattern(+).
Other four arms are, left arm = (2, 2), right arm = (2, 4),
up arm = (1, 3), down arm = (2, 3).
Hence sum of all elements are ( 1 + 1 + (-4) + 1 + 1 ) = 0.
Input: N = 5, M = 3
1 2 3
-6 1 -4
1 1 1
7 8 9
6 3 2
Output: 31
Approach: This problem is an application of the standard Largest Sum Contiguous Subarray.
We quickly pre-compute the maximum contiguous sub-sequence (subarray) sum for each row and column, in 4 directions, namely, Up, Down, Left and Right. This can be done using the standard Maximum contiguous sub-sequence sum of a 1-D array.
We make four 2-D array’s 1 for each direction.
- up[i][j]– Maximum sum contiguous sub-sequence of elements in upward direction, from rows 1, 2, 3, …, i More formally, it represents the maximum sum obtained by adding a contiguous sub-sequence of elements from list of arr[1][j], arr[2][j], …, arr[i][j]
- down[i][j] -Maximum sum contiguous sub-sequence of elements in downward direction, from rows i, i+1, i+2,,…, N More formally, it represents the maximum sum obtained by adding a contiguous sub-sequence of elements from list of arr[i][j], arr[i+1][j], …, arr[N][j]
- left[i][j]– Maximum sum contiguous sub-sequence of elements in left direction, from columns 1, 2, 3, …, j More formally, it represents the maximum sum obtained by adding a contiguous sub-sequence of elements from list of arr[i][1], arr[i][2], …, arr[i][j]
- right[i][j]– Maximum sum contiguous sub-sequence of elements in right direction, from columns j, j+1, j+2, …, M More formally, it represents the maximum sum obtained by adding a contiguous sub-sequence of elements from list of arr[i][j], arr[i][j+1], …, arr[i][M]
All that’s left is, to check each cell as a possible center of the + and use pre-computed data to find the value achieved by + shape in O(1). ![Ans_{i, j} = up[i-1][j] + down[i+1][j] + left[i][j-1]+right[i][j+1]+arr[i][j]_{adding\;the\;value\;at \;center\; of\; +}](https://geeksforgeeks.org/wp-content/uploads/2023/11/dominic_rubhabha_quicklatex.com-85b2556b416833463c94221bb5a0ccea_l3.png "Rendered by QuickLaTeX.com")
Below is the implementation of the above approach:
C++
// C++ program to find the maximum value// of a + shaped pattern in 2-D array#include <bits/stdc++.h>using namespace std;#define N 100const int n = 3, m = 4;// Function to return maximum Plus valueint maxPlus(int (&arr)[n][m]){ // Initializing answer with the minimum value int ans = INT_MIN; // Initializing all four arrays int left[N][N], right[N][N], up[N][N], down[N][N]; // Initializing left and up array. for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { left[i][j] = max(0LL, (j ? left[i][j - 1] : 0LL)) + arr[i][j]; up[i][j] = max(0LL, (i ? up[i - 1][j] : 0LL)) + arr[i][j]; } } // Initializing right and down array. for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { right[i][j] = max(0LL, (j + 1 == m ? 0LL: right[i][j + 1])) + arr[i][j]; down[i][j] = max(0LL, (i + 1 == n ? 0LL: down[i + 1][j])) + arr[i][j]; } } // calculating value of maximum Plus (+) sign for (int i = 1; i < n - 1; ++i) for (int j = 1; j < m - 1; ++j) ans = max(ans, up[i - 1][j] + down[i + 1][j] + left[i][j - 1] + right[i][j + 1] + arr[i][j]); return ans;}// Driver codeint main(){ int arr[n][m] = { { 1, 1, 1, 1 }, { -6, 1, 1, -4 }, { 1, 1, 1, 1 } }; // Function call to find maximum value cout << maxPlus(arr); return 0;} |
Java
// Java program to find the maximum value // of a + shaped pattern in 2-D array class GFG { public static int N = 100; public static int n = 3, m = 4; // Function to return maximum Plus value public static int maxPlus(int[][] arr) { // Initializing answer with the minimum value int ans = Integer.MIN_VALUE; // Initializing all four arrays int[][] left = new int[N][N]; int[][] right = new int[N][N]; int[][] up = new int[N][N]; int[][] down = new int[N][N]; // Initializing left and up array. for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { left[i][j] = Math.max(0, ((j != 0) ? left[i][j - 1] : 0)) + arr[i][j]; up[i][j] = Math.max(0, ((i != 0)? up[i - 1][j] : 0)) + arr[i][j]; } } // Initializing right and down array. for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { right[i][j] = Math.max(0, (j + 1 == m ? 0: right[i][j + 1])) + arr[i][j]; down[i][j] = Math.max(0, (i + 1 == n ? 0: down[i + 1][j])) + arr[i][j]; } } // calculating value of maximum Plus (+) sign for (int i = 1; i < n - 1; ++i) for (int j = 1; j < m - 1; ++j) ans = Math.max(ans, up[i - 1][j] + down[i + 1][j] + left[i][j - 1] + right[i][j + 1] + arr[i][j]); return ans; } // Driver code public static void main(String[] args) { int[][] arr = new int[][]{ { 1, 1, 1, 1 }, { -6, 1, 1, -4 }, { 1, 1, 1, 1 } }; // Function call to find maximum value System.out.println( maxPlus(arr) ); }}// This code is contributed by PrinciRaj1992. |
Python 3
# Python 3 program to find the maximum value# of a + shaped pattern in 2-D arrayN = 100n = 3m = 4# Function to return maximum# Plus valuedef maxPlus(arr): # Initializing answer with # the minimum value ans = 0 # Initializing all four arrays left = [[0 for x in range(N)] for y in range(N)] right = [[0 for x in range(N)] for y in range(N)] up = [[0 for x in range(N)] for y in range(N)] down = [[0 for x in range(N)] for y in range(N)] # Initializing left and up array. for i in range(n) : for j in range(m) : left[i][j] = (max(0, (left[i][j - 1] if j else 0)) + arr[i][j]) up[i][j] = (max(0, (up[i - 1][j] if i else 0)) + arr[i][j]) # Initializing right and down array. for i in range(n) : for j in range(m) : right[i][j] = max(0, (0 if (j + 1 == m ) else right[i][j + 1])) + arr[i][j] down[i][j] = max(0, (0 if (i + 1 == n ) else down[i + 1][j])) + arr[i][j] # calculating value of maximum # Plus (+) sign for i in range(1, n - 1): for j in range(1, m - 1): ans = max(ans, up[i - 1][j] + down[i + 1][j] + left[i][j - 1] + right[i][j + 1] + arr[i][j]) return ans# Driver codeif __name__ == "__main__": arr = [[ 1, 1, 1, 1 ], [ -6, 1, 1, -4 ], [ 1, 1, 1, 1 ]] # Function call to find maximum value print(maxPlus(arr))# This code is contributed # by ChitraNayal |
C#
// C# program to find the maximum value // of a + shaped pattern in 2-D array using System; class GFG { public static int N = 100; public static int n = 3, m = 4; // Function to return maximum Plus value public static int maxPlus(int[,] arr) { // Initializing answer with the minimum value int ans = int.MinValue; // Initializing all four arrays int[,] left = new int[N,N]; int[,] right = new int[N,N]; int[,] up = new int[N,N]; int[,] down = new int[N,N]; // Initializing left and up array. for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { left[i,j] = Math.Max(0, ((j != 0) ? left[i,j - 1] : 0)) + arr[i,j]; up[i,j] = Math.Max(0, ((i != 0)? up[i - 1,j] : 0)) + arr[i,j]; } } // Initializing right and down array. for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { right[i,j] = Math.Max(0, (j + 1 == m ? 0: right[i,j + 1])) + arr[i,j]; down[i,j] = Math.Max(0, (i + 1 == n ? 0: down[i + 1,j])) + arr[i,j]; } } // calculating value of maximum Plus (+) sign for (int i = 1; i < n - 1; ++i) for (int j = 1; j < m - 1; ++j) ans = Math.Max(ans, up[i - 1,j] + down[i + 1,j] + left[i,j - 1] + right[i,j + 1] + arr[i,j]); return ans; } // Driver code static void Main() { int[,] arr = new int[,]{ { 1, 1, 1, 1 }, { -6, 1, 1, -4 }, { 1, 1, 1, 1 } }; // Function call to find maximum value Console.Write( maxPlus(arr) ); }}// This code is contributed by DrRoot_ |
Javascript
<script>// JavaScript program to find the maximum value // of a + shaped pattern in 2-D array let N = 100; let n = 3, m = 4; //Function to return maximum Plus value function maxPlus(arr) { // Initializing answer with the minimum value let ans = 0; // Initializing all four arrays let left = new Array(N); let right = new Array(N); let up = new Array(N); let down = new Array(N); for(let i=0;i<N;i++) { left[i]=new Array(N); right[i]=new Array(N); up[i]=new Array(N); down[i]=new Array(N); for(let j=0;j<N;j++) { left[i][j]=0; right[i][j]=0; up[i][j]=0; down[i][j]=0; } } // Initializing left and up array. for (let i = 0; i < n; i++) { for (let j = 0; j < m; j++) { left[i][j] = Math.max(0, ((j != 0) ? left[i][j - 1] : 0)) + arr[i][j]; up[i][j] = Math.max(0, ((i != 0)? up[i - 1][j] : 0)) + arr[i][j]; } } // Initializing right and down array. for (let i = 0; i < n; i++) { for (let j = 0; j < m; j++) { right[i][j] = Math.max(0, (j + 1 == m ? 0: right[i][j + 1])) + arr[i][j]; down[i][j] = Math.max(0, (i + 1 == n ? 0: down[i + 1][j])) + arr[i][j]; } } // calculating value of maximum Plus (+) sign for (let i = 1; i < n - 1; ++i) for (let j = 1; j < m - 1; ++j) { ans = Math.max(ans, up[i - 1][j] + down[i + 1][j] + left[i][j - 1] + right[i][j + 1] + arr[i][j]); } return ans; } // Driver code let arr = [[ 1, 1, 1, 1 ], [ -6, 1, 1, -4 ], [ 1, 1, 1, 1 ]]; document.write(maxPlus(arr)); // This code is contributed by avanitrachhadiya2155</script> |
Output
0
Time Complexity: O(N*M) for given N rows and M columns
Auxiliary Space: O(N*M)
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!
