Maximum value of a plus shaped pattern in a 2D array

Updated

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;
}
Comment
Mithlesh Upadhyay Published 22 Nov 2026 · 4 min read

Mithlesh Upadhyay is a Computer Science and AI expert from Madhya Pradesh with strong academic background (BE in CSE and M.Tech in AI) and over six years of experience in technical content development. He has contributed tech articles, led teams, and worked in Full Stack Development and Data Science. He founded the w3colleges.org portal for learning resources.

Related tutorials