Iterative DP. Time: O(rowsxcols), Space: O(cols)
Approach\n Describe your approach to solving the problem. \nTraverse matrix from bottom right exploring both options for each cells - bottom or to the right. St
# Approach\n<!-- Describe your approach to solving the problem. -->\nTraverse matrix from bottom right exploring both options for each cells - bottom or to the right. Store the values in a 1-d array which will be updated as we move up the rows.\n\n# Complexity\n- Time complexity: $$O(ROWSxCOLS)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(COLS)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```python []\nclass Solution(object):\n    def maxScore(self, grid):\n        """\n        :type grid: List[List[int]]\n        :rtype: int\n        """\n        ROWS = len(grid)\n        COLS = len(grid[0])\n        col_opt = [0]*COLS\n\n        res = float("-inf")\n        col_opt[-1] = grid[-1][-1]\n        max_so_far = grid[-1][-1]\n        for c in range(COLS-2,-1,-1):\n            res = max(res, max_so_far - grid[-1][c])\n            col_opt[c] = max(grid[-1][c], max_so_far)\n            max_so_far = max(max_so_far, grid[-1][c])\n        \n\n        #print col_opt\n        #print res\n\n        for r in range(ROWS-2,-1,-1):\n            res = max(res, col_opt[-1] - grid[r][-1])\n            col_opt[-1] =  max(grid[r][-1],col_opt[-1])\n\n            max_in_cur_col = col_opt[-1]\n\n            #print "row:",r,"col:",col_opt, res, max_in_cur_col\n\n            for c in range(COLS-2,-1,-1):\n                res = max(res, max(col_opt[c],max_in_cur_col)- grid[r][c])\n\n                #print "row:",r,"col:",col_opt, res\n\n                col_opt[c] = max(grid[r][c], max(max_in_cur_col, col_opt[c]))\n\n                max_in_cur_col = max(max_in_cur_col, col_opt[c])\n\n        return res        \n\n```
['Python']