Given a 2D array, find the maximum sum subarray in it. For example, in the following 2D array, the maximum sum subarray is highlighted with blue rectangle and sum of this subarray is 29.

Given a 2D array, find the maximum sum subarray in it. For example, in the following 2D array, the maximum sum subarray is highlighted with a blue rectangle, and the sum of this subarray is 29.

Here is simple and easy solution with execution time 0.01s.

#include <bits/stdc++.h>

using namespace std;

int main() {
    //code
    int t;
    cin >> t;
    while (t--) {
        long int n, m, x;
        cin >> n >> m;
        vector < vector < long int > > v(n, vector < long int > (m));
        for (int i = 0; i < n; ++i) {

            for (int j = 0; j < m; ++j) {
                cin >> x;
                v[i][j] = x;
            }

        }


        long long int curmax = INT_MIN, summax = INT_MIN, mxup = 0, mxright = -1, mxleft = -1, mxdown = -1;

        for (int i = 0; i < m; ++i) {
            mxleft = i;
            vector < long int > temp(n), temp2(n);
            for (int p = 0; p < n; ++p)
                temp[p] = 0;


            for (int j = i; j < m; ++j) {
                //               cout<<j<<endl;
                for (int k = 0; k < n; ++k) {

                    //          cout<<v[k][j]<<" ";
                    temp[k] = temp[k] + v[k][j];

                    //                    cout<<temp[k]<<" ";
                }
                //                 for(int p=0;p<n;++p)
                //                cout<<temp[p]<<" ";
                mxright = j, mxup = 0;
                long long int global = INT_MIN, local = 0, mxcurrent = 0;
                for (int l = 0; l < n; ++l) {
                    local += temp[l];
                    if (local < 0) {
                        local = 0;
                        mxcurrent = l + 1;
                    }
                    if (local > global) {
                        global = local, mxdown = l, mxup = mxcurrent;
                    }

                }

                //                cout<<local<<" "<<global<<endl;

                if (global > summax) {
                    summax = global;
                }
            }
        }
        cout << summax << endl;
    }
    return 0;
}