DP Solution | Easy Approach | O(n^2) | Space Optimised
Intuition\nIt can be observed that for every index except last one, we have two options to traverse: Rightwards and Downwards. We can avoid many computations by
# Intuition\nIt can be observed that for every index except last one, we have two options to traverse: Rightwards and Downwards. We can avoid many computations by traversing bottom-right to top-left.\n\nDry Run:\n------------\n \nArray: \n\n[[ 9 5  7 3 ],\n[ 8 9  6 1 ],\n[ 6 7 14 3 ],\n[ 2 5  3 1 ]]\n\nDP Array:\n\n[[ 5  9   7    0 ],\n[ 6  5   8     2 ],\n[ 8  7  -11   -2 ],\n[ 3 -2  -2  -1e5 ]]\n\n# Approach\nTraverse from bottom right to top-left and try to store maxValue in DP.\n\n# Complexity\n- Time complexity: $$O(n*m)$$\n\n- Space complexity: $$O(n)$$\n\n# Code\n```\nclass Solution {\npublic:\n    int maxScore(vector<vector<int>>& grid) {\n        int n = grid.size(), m = grid[0].size();\n        vector<vector<int>> dp(n, vector<int>(m, -1e5));\n\n        // Last Option is not valid , so it is set as -1e5.\n        int maxAns = INT_MIN;\n        // Fill dp for the bottom row (except the last cell)\n        for (int j = m - 2; j >= 0; j--) {\n            dp[n - 1][j] =\n                max(grid[n - 1][j + 1] - grid[n - 1][j] + dp[n - 1][j + 1],\n                    grid[n - 1][j + 1] - grid[n - 1][j]);\n            maxAns = max(maxAns, dp[n - 1][j]);\n        }\n\n        // Fill dp for the right column (except the last cell)\n        for (int i = n - 2; i >= 0; i--) {\n            dp[i][m - 1] =\n                max(grid[i + 1][m - 1] - grid[i][m - 1] + dp[i + 1][m - 1],\n                    grid[i + 1][m - 1] - grid[i][m - 1]);\n            maxAns = max(maxAns, dp[i][m - 1]);\n        }\n\n        // Fill dp for the rest of the grid (bottom to top, right to left)\n        for (int i = n - 2; i >= 0; i--) {\n            for (int j = m - 2; j >= 0; j--) {\n                dp[i][j] = max(max(grid[i][j + 1] - grid[i][j] + dp[i][j + 1],\n                                   grid[i][j + 1] - grid[i][j]),\n                               max(grid[i + 1][j] - grid[i][j] + dp[i + 1][j],\n                                   grid[i + 1][j] - grid[i][j]));\n                maxAns = max(maxAns, dp[i][j]);\n            }\n        }\n\n        return maxAns;\n    }\n};\n\n```\n\n## Space Optimised Code\n```\nclass Solution {\npublic:\n    int maxScore(vector<vector<int>>& grid) {\n        int n = grid.size(), m = grid[0].size();\n        vector<int> dp(m, -1e5);  \n        int maxAns = INT_MIN;\n        // Fill dp for the bottom row (except the last cell)\n        for (int j = m - 2; j >= 0; j--) {\n            dp[j] = max(grid[n - 1][j + 1] - grid[n - 1][j] + dp[j + 1],\n                        grid[n - 1][j + 1] - grid[n - 1][j]);\n            maxAns = max(maxAns, dp[j]);\n        }\n\n        // Temporary vector to store the previous row\'s dp values\n        vector<int> prev_dp = dp;\n\n        // Fill dp for the rest of the grid (bottom to top, right to left)\n        for (int i = n - 2; i >= 0; i--) {\n            dp[m - 1] = max(grid[i + 1][m - 1] - grid[i][m - 1] + prev_dp[m - 1],\n                            grid[i + 1][m - 1] - grid[i][m - 1]);\n            maxAns = max(maxAns, dp[m - 1]);\n            for (int j = m - 2; j >= 0; j--) {\n                dp[j] = max(max(grid[i][j + 1] - grid[i][j] + dp[j + 1],\n                                grid[i][j + 1] - grid[i][j]),\n                            max(grid[i + 1][j] - grid[i][j] + prev_dp[j],\n                                grid[i + 1][j] - grid[i][j]));\n                maxAns = max(maxAns, dp[j]);\n            }\n            prev_dp = dp;\n        }\n\n        return maxAns;\n    }\n};\n```\n
['C++']