C++ solution #intution_simpleAF
Intuition\nWe can see that we can only move down and right, and taking as many jumps in between, for a certain start and certain end, it doesn\'t matter what pa
# Intuition\nWe can see that we can only move down and right, and taking as many jumps in between, for a certain start and certain end, it doesn\'t matter what path we take, the final score will be the same.\n\n# Approach\nI make another grid named matrix where we store at any index(i,j), the maximum in the sub-grid(n,m), where i<=n<=grid.size() and j<=m<=grid[0].size(). We can make that happen but iterating in turns, like firstly, for point (i,j)\n1. We move from (i->0 to n-1) and in the nested loop we move (j->m-1 to 0) and carry the maximum to (i,0). We do it till i==0.\n\n2. Now we move from (j->m-1 to 0) and in the nested loop we move(i->n-1 to 0), we carry maximum to the top (0,j). we do it till j==0.\n\nNote that we move the iterator in the direction from right to left for each row and then from bottom to top in each column.\n\nNow, we carry out the calculation for maximum score i.e. for any index(i,j) the maximum score will be [matrix[i][j] - grid[i][j]]. And we iterate over the whole range to find the max score. If the score is 0, then we can see that either all the values are equal or they are in decreasing order in all sequences from (left to right) and (top to bottom). Then we use the difference between adjacent elements and find the maximum diff as the ans.\n\nP.S. implementation is tough, the overall thought process is simple.\n\n# Complexity\n- Time complexity:\nIt would be O(N*M) which is same to traverse the grid.\n\n- Space complexity:\nIt is O(N*M) as we are using another grid to store the maximum in any sub-grid.\n\n# Code\n```\nclass Solution {\npublic:\n    int maxScore(vector<vector<int>>& grid) {\n        vector<vector<int>> matrix;\n        for (int j = 0; j < grid.size(); j++)\n        {\n            vector<int> vp = grid[j];\n            int r = vp[vp.size() - 1];\n            for (int p = vp.size() - 2; p >= 0; p--)\n            {\n                if (vp[p] < r)\n                {\n                    vp[p] = r;\n                }\n                else\n                {\n                    r = vp[p];\n                }\n            }\n            matrix.push_back(vp);\n        }\n        for (int j = grid[0].size() - 1; j >= 0; j--)\n        {\n            int r = matrix[matrix.size() - 1][j];\n            for (int k = grid.size() - 2; k >= 0; k--)\n            {\n                if (matrix[k][j] < r)\n                {\n                    matrix[k][j] = r;\n                }\n                else\n                {\n                    r = matrix[k][j];\n                }\n            }\n        }\n        int ml = INT_MIN;\n        for (int i = 0; i < grid.size(); i++)\n        {\n            for (int j = 0; j < grid[0].size(); j++)\n            {\n                ml = max(ml, matrix[i][j] - grid[i][j]);\n            }\n        }\n        if (ml == 0)\n        {\n            int mk = INT_MIN;\n            for (int j = 0; j < grid.size(); j++)\n            {\n                for (int k = 1; k < grid[0].size(); k++)\n                {\n                    mk = max(grid[j][k] - grid[j][k - 1], mk);\n                }\n            }\n            for (int j = grid[0].size() - 1; j >= 0; j--)\n            {\n                for (int k = grid.size() - 1; k > 0; k--)\n                {\n                    mk = max(mk, grid[k][j] - grid[k - 1][j]);\n                }\n            }\n            return mk;\n        }\n        else\n        {\n            return ml;\n        }\n    }\n};\n```
['C++']