> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/dynamic-programming/max-sum-without-adjacent-elements.md).

# Max Sum Without Adjacent Elements

Given a **2 x N** grid of integer, **A**, choose numbers such that the sum of the numbers\
is maximum and **no** two chosen numbers are adjacent horizontally, vertically or diagonally, and return it.

**Note:** You can choose more than 2 numbers.

**Input Format:**

```
The first and the only argument of input contains a 2d matrix, A.
```

**Output Format:**

```
Return an integer, representing the maximum possible sum.
```

**Constraints:**

```
1 <= N <= 20000
1 <= A[i] <= 2000
```

**Example:**

```
Input 1:
    A = [   [1]
            [2]    ]

Output 1:
    2

Explanation 1:
    We will choose 2.

Input 2:
    A = [   [1, 2, 3, 4]
            [2, 3, 4, 5]    ]
    
Output 2:
    We will choose 3 and 5.
```

```java
public class Solution {
    public int adjacent(int[][] A) {
        if (A[0].length == 1)
            return Math.max(A[0][0], A[1][0]);
        int m = A[0].length;
        // 0th index best
        int prev_max = Math.max(A[0][0], A[1][0]);
        // 1st index best
        int curr_max = Math.max(prev_max, Math.max(A[0][1], A[1][1]));
        for (int j = 2; j < m; j++) {
            int temp = curr_max;
            curr_max = Math.max(Math.max(A[0][j], A[1][j]) + prev_max, curr_max);
            prev_max = temp;
        }
        return curr_max;
    }
}
```