How do I choose elements in a 2D array such that no two elements are adjacent and that their sum is maximum?

I am given ann5 matrixAconsisting of integers (positive or negative). How do I find a setSof tuples (i,j) indicating locations of the 2-D matrixAsuch that:

1. The sum of elements is maximized
2. No elements are adjacent to one another.

2. You are given an n 5 matrix A consisting of integers (positive or negative). Your goal is to find a set S of tuples (i, j) indicating locations of the 2-D matrix A such that: 1. (i,j)es A[i, j] is maximized, and - 2. For all pairs of tuples (1, 1), (12, j2) S, (i2, j2) {(i1 1, j1), (i1 +1, j), (1, j1 1), (1, j1 + 1)}. (For example, consider the 2 5 matrix below. The set of locations that satisfies (1) and (2) above are indicated by shading these locations in the matrix.) -1 2 3 2 -4 5 -5356 Design an algorithm for this problem. Give pseudocode. Discuss running time and give proof of correct- ness.