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

  • 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);
}