We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. Matrix Land
  5. Discussions

Matrix Land

Sort by

recency

|

13 Discussions

|

  • dehaka
     + 0 comments

    stupid dumbass question, my algo is O(n*m), a high multiple of n*m but the question still times out, and doesnt give enough memory. had to use a lot of push_back instead of create the storage vectors beforehand, and create storage on the heap to avoid memory issues

    this pass all test and has no memory issues no time out

    int matrixLand(int n, int m, const vector<vector<int>>& A) {
    vector<vector<int>>* prev = new vector<vector<int>>();
    vector<vector<int>>* current = new vector<vector<int>>();
    for (int i = 0; i < n; i++) {
        vector<vector<int>> row = { {A[i][0]} };
        for (int j = 1; j < m; j++) row.push_back({ max(row[j - 1][0] + A[i][j], A[i][j]) });
        row[m-1].push_back(A[i][m-1]);
        row[m-1].push_back(A[i][m-1]);
        for (int j = m - 2; j >= 0; j--) {
            row[j].push_back(max(row[j + 1][1] + A[i][j], A[i][j]));
            row[j].push_back(row[j][0] + max(row[j + 1][1], 0));
        }
        if (i == 0) {
            *prev = row;
            current = prev;
            continue;
        }
        current = new vector<vector<int>>({{ (*prev)[0][1]+A[i][0] }});
        for (int j = 1; j < m; j++) {
            int a = (*current)[j - 1][0] + A[i][j];
            int b = (*prev)[j][1] + row[j][0];
            int c = (*prev)[j][2] + A[i][j];
            (*current).push_back({ max({ a, b, c }) });
        }
        (*current)[m-1].push_back((*prev)[m-1][0] + A[i][m-1]);
        (*current)[m-1].push_back((*current)[m-1][1]);
        for (int j = m - 2; j >= 0; j--) {
            int a = (*current)[j + 1][1] + A[i][j];
            int b = (*prev)[j][0] + row[j][1];
            int c = (*prev)[j][2] + A[i][j];
            (*current)[j].push_back(max({ a, b, c }));
            int x = (*current)[j][0] + max(row[j + 1][1], 0);
            int y = (*prev)[j][2] + row[j][2];
            int z = (*current)[j + 1][1] + row[j][0];
            (*current)[j].push_back(max({ x, y, z }));
        }
        delete prev;
        prev = current;
    }
    int answer = 0;
    for (int j = 0; j < m; j++) answer = max(answer, (*current)[j][0]);
    return answer;
}

int main()
{
    int n, m, k;
    vector<vector<int>> A;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        A.emplace_back();
        for (int j = 0; j < m; j++) {
            cin >> k;
            A[i].push_back(k);
        }
    }
    cout << matrixLand(n, m, A);
}

  • yashparihar729
     + 0 comments

    Here is my solution in java, javascript, python, C, C++, Csharp HackerRank Matrix Land Problem Solution

  • eiduladh_a_wish1
     + 0 comments

    Is it help me in my Laser Grading system to calculate and level the land in proper way.

  • thecodingsoluti2
     + 0 comments

    Here is Matrix Land problem solution - https://programs.programmingoneonone.com/2021/07/hackerrank-matrix-land-problem-solution.html

  • shehanjayalath
     + 1 comment

    C++ Solution

    #include <iostream>
#include <string>
#include <cmath>
using namespace std;

long long V[5000000], L[5000000], R[5000000], XL[5000000], XR[5000000], T[5000000];

void print(int M, long long (&TT)[5000000]) {
    for(int i=0; i<M; i++) {
        cout << " " << TT[i];
    }
    cout << endl;
}

int main() {
    std::ios::sync_with_stdio(false);
    int N, M;
    while(cin >> N >> M) {
        for(int i=0; i<M; i++)
            T[i] = 0;

        for(int i=0; i<N; i++) {
            for(int j=0; j<M; j++)
                cin >> V[j];
            
            long long vl = 0, vr = 0;
            for(int j=0; j<M; j++) {
                vl = L[j] = max(vl + V[j], V[j]);
                vr = R[M-j-1] = max(vr + V[M-j-1], V[M-j-1]);
            }
            
            vl = vr = -200000000000000000ll;
            for(int j=0; j<M; j++) {
                vl = XL[j] = max(vl + V[j], T[j] + L[j]);
                vr = XR[M-j-1] = max(vr + V[M-j-1], T[M-j-1] + R[M-j-1]);
            }
            
            for(int j=0; j<M; j++) {
                T[j] = max(
                    XL[j] + (j+1 < M ? max(R[j+1], 0ll) : 0ll),
                    XR[j] + (j-1 < M ? max(L[j-1], 0ll) : 0ll)
                );
            }
        }
        
        long long answer = -200000000000000000ll;
        for(int i=0; i<M; i++) {
            answer = max(answer, T[i]);
        }
        cout << answer << endl;
    }
    
}