I tried to write a dynamic program to solve the following problem.

Given a $ n \times m$ matrix $ A$ , select a one element per row in order to maximize the following measure $ m$ :

- Each selected element $ a_{i,j}$ that is on the last row $ (i=n)$ or directly above the element $ a_{i-1,j}$ selected in the previous row contributes $ a_{i,j}$ to $ m$ .
- Each element $ a_{i,j}$ that is not on the last row and not directly above the element selected in the previous row contributes $ -a_{i,j}$ to $ m$ .

For example:

Matrix: $ $ \begin{bmatrix} 4 & 9 & 4 \ 3 & 1 & 2 \ 3 & 5 & 8 \ \end{bmatrix} $ $

Output: 16 (8 – 1 + 9) (From bottom row to top)

Another example:

Grid:

$ $ \begin{bmatrix} 9 & 2 & 1 & 3 \ 3 & 7 & 6 & 1 \ 1 & 2 & 3 & 9 \end{bmatrix} $ $

Output: 15 (9 – 3 + 9) (From bottom row to top)

My idea is to compare between 3+3+4 and 3-1+9 and 3-2+4 and so on.

Here is my method of doing it:

`int row, col; int max_score(vector<vector<int> > grid, int r, int c) { int result = 0; if(c > 0 && c < col - 1 && r > 0) { result = max_score(grid, r-1, c) + grid[r-1][c]; result = max(result, max_score(grid, r-1, c-1) - grid[r-1][c-1]); result = max(result, max_score(grid, r-1, c+1) - grid[r-1][c+1]); } else if(c == 0 && r > 0) { result = max_score(grid, r-1, c) + grid[r-1][c]; result = max(result, max_score(grid, r-1, c+1) - grid[r-1][c+1]); } else if(c == col - 1 && r > 0) { result = max_score(grid, r-1, c) + grid[r-1][c]; result = max(result, max_score(grid, r-1, c-1) - grid[r-1][c-1]); } return result; } int main() { int a, result; cin >> row >> col; vector<vector<int> > grid( row , vector<int> (col)); for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++){ cin >> a; grid[i][j] = a; } } for(int i = row - 1; i > 0; i--) { for(int j = 0; j < col; j++) { result = max_score(grid, i, j); } } cout << result << endl; return 0; } `

I was getting the wrong result of this. Any suggestion will help. Thank you!