Video Explanation [Optimising  N*M*(N+M) solution step by step to N*M]
Explanation\n\nClick here for the video\n\n# Code\n\ntypedef long long int ll;\n\nconst ll INF = 1e18;\n\nclass Solution {\n    vector<vector<ll>> dp;\n    vect
# Explanation\n\n[Click here for the video](https://youtu.be/pF3XT6cDHpU)\n\n# Code\n```\ntypedef long long int ll;\n\nconst ll INF = 1e18;\n\nclass Solution {\n    vector<vector<ll>> dp;\n    vector<vector<int>> grid;\n    int rows, cols;\n    \n    /*\n    ll MaxScore (int r, int c) {\n        if (r == rows-1 && c == cols-1) return -INF;\n        \n        ll& ans = dp[r][c];\n        if (ans != -INF) return ans;\n        \n        for (int rgt = c+1; rgt < cols; rgt ++) {\n            ans = max(ans, (ll)grid[r][rgt] - grid[r][c] + max(0LL, MaxScore(r, rgt)));\n        }\n        for (int dwn = r+1; dwn < rows; dwn ++) {\n            ans = max(ans, (ll)grid[dwn][c] - grid[r][c] + max(0LL, MaxScore(dwn, c)));\n        }\n        return ans;\n    } \n    */\n    \npublic:\n    \n    /*\n    int maxScore(vector<vector<int>>& _grid) {\n        grid = _grid;\n        rows = grid.size();\n        cols = grid[0].size();\n        \n        dp.clear();\n        dp.resize (rows+1, vector<ll>(cols+1, -INF));\n        \n        ll ans = -INF;\n        for (int r = 0; r < rows; r ++)\n            for (int c = 0; c < cols; c++) ans = max(ans, MaxScore(r, c));\n        return ans;\n    }\n    */\n    \n    int maxScore(vector<vector<int>>& grid) {\n        int rows = grid.size();\n        int cols = grid[0].size();\n        \n        vector<vector<ll>> max_val (rows+1, vector<ll>(cols+1, INT_MIN));\n        vector<vector<ll>> max_rgt (rows+1, vector<ll>(cols+1, INT_MIN));\n        vector<vector<ll>> max_dwn (rows+1, vector<ll>(cols+1, INT_MIN));\n        \n        for (int c = cols-1; c >= 0; c --) {\n            for (int r = rows-1; r >= 0; r --) {                \n                max_val[r][c] = max ({max_rgt[r][c+1], max_dwn[r+1][c]}) - grid[r][c];\n                max_rgt[r][c] = max ({max_rgt[r][c+1],  grid[r][c] + max_val[r][c],  (ll)grid[r][c]});\n                max_dwn[r][c] = max ({max_dwn[r+1][c],  grid[r][c] + max_val[r][c],  (ll)grid[r][c]});\n            }\n        }\n        \n        ll ans = -1e18;\n        for (auto r: max_val)\n            for (auto c: r) ans = max(ans, c);\n        return ans;\n    }\n};\n```
['C++']