Given a 2-D array of size N*M where, 3\(\leq\) N,M \(\leq\) 1000 . The task is to find the maximum value achievable by a + shaped pattern. The elements of the array can be negative.
Examples :
Input : 3 4
1 1 1 1
-6 1 1 -4
1 1 1 1
Output : 0
Approach :
This problem is an application of 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\; +}\) Below is the implementation of above approach.
Implementation :
// C++ program to find the maximum value
// of a + shaped pattern in 2-D array
#include <bits/stdc++.h>
using namespace std;
#define N 100
const int n=3,m=4;
// function to return maximum Plus value
int maxPlus(int (&arr)[n][m]){
int ans=INT_MIN,val;
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 maximum Plus sign value
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 program
int 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;
}