Problem

Given a 2 x N grid of integers A (two rows and N columns), choose a set of elements with maximum possible sum such that no two selected elements are adjacent horizontally, vertically or diagonally.

Example

1
2
3
4
5

Input:
A = [[1,2,3,4],
     [2,3,4,5]]

One optimal selection: pick 3 (row0,col2) and 5 (row1,col3) => sum = 8
Similar Problems

Solution

We present two standard approaches. Both run in linear time O(N) and use constant extra space.

Method 1 — Reduce to 1D then apply House-Robber DP

Intuition

For each column i you’re never going to pick both elements in the same column because they are vertically adjacent. So the only sensible contribution from column i is the larger of the two values: colMax[i] = max(A[0][i], A[1][i]). Once reduced to the array colMax, the adjacency constraint between columns forbids selecting adjacent columns — this is exactly the classic House Robber problem.

Approach

  • Use the standard two-variable DP for House Robber: maintain incl (best including previous column) and excl (best excluding previous column):
    • new_excl = max(excl, incl)
    • incl = excl + colMax[i]
    • excl = new_excl

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
 public:
  long long maxSum2xN(const std::vector<std::vector<long long>>& A) {
    int n = A[0].size();
    if (n == 0) return 0;
    std::vector<long long> colMax(n);
    for (int i = 0; i < n; ++i) colMax[i] = std::max(A[0][i], A[1][i]);

    long long incl = 0; // max sum including previous
    long long excl = 0; // max sum excluding previous
    for (int i = 0; i < n; ++i) {
      long long new_excl = std::max(excl, incl);
      incl = excl + colMax[i];
      excl = new_excl;
    }
    return std::max(excl, incl);
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

package main

func maxSum2xN(A [][]int64) int64 {
    n := len(A[0])
    if n == 0 {
        return 0
    }
    colMax := make([]int64, n)
    for i := 0; i < n; i++ {
        if A[0][i] > A[1][i] {
            colMax[i] = A[0][i]
        } else {
            colMax[i] = A[1][i]
        }
    }
    var incl, excl int64 = 0, 0
    for i := 0; i < n; i++ {
        newExcl := excl
        if incl > excl {
            newExcl = incl
        }
        incl = excl + colMax[i]
        excl = newExcl
    }
    if incl > excl { return incl }
    return excl
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
  public long maxSum2xN(long[][] A) {
    int n = A[0].length;
    if (n == 0) return 0;
    long[] colMax = new long[n];
    for (int i = 0; i < n; ++i) colMax[i] = Math.max(A[0][i], A[1][i]);

    long incl = 0L, excl = 0L;
    for (int i = 0; i < n; ++i) {
      long newExcl = Math.max(excl, incl);
      incl = excl + colMax[i];
      excl = newExcl;
    }
    return Math.max(excl, incl);
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def max_sum_2xN(self, A: list[list[int]]) -> int:
        n = len(A[0])
        if n == 0:
            return 0
        col_max = [max(A[0][i], A[1][i]) for i in range(n)]

        incl = 0  # best including previous column
        excl = 0  # best excluding previous column
        for v in col_max:
            new_excl = excl if excl > incl else incl
            incl = excl + v
            excl = new_excl
        return excl if excl > incl else incl

Complexity

Method 2 — Direct two-state column DP (space-optimized)

Intuition

Instead of creating colMax, directly process each column and maintain two values: incl (best sum including current column) and excl (best sum excluding current column). For a column i, including it contributes max(A[0][i], A[1][i]) plus the previous excl value.

Approach

  • new_excl = max(excl, incl)
  • incl = excl + max(A[0][i], A[1][i])
  • excl = new_excl

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
 public:
  long long maxSum2xN_direct(const std::vector<std::vector<long long>>& A) {
    int n = A[0].size();
    if (n == 0) return 0;
    long long incl = std::max(A[0][0], A[1][0]);
    long long excl = 0;
    for (int i = 1; i < n; ++i) {
      long long new_excl = std::max(excl, incl);
      incl = excl + std::max(A[0][i], A[1][i]);
      excl = new_excl;
    }
    return std::max(incl, excl);
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
  public long maxSum2xN_direct(long[][] A) {
    int n = A[0].length;
    if (n == 0) return 0;
    long incl = Math.max(A[0][0], A[1][0]);
    long excl = 0;
    for (int i = 1; i < n; ++i) {
      long newExcl = Math.max(excl, incl);
      incl = excl + Math.max(A[0][i], A[1][i]);
      excl = newExcl;
    }
    return Math.max(incl, excl);
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def max_sum_2xN_direct(self, A: list[list[int]]) -> int:
        n = len(A[0])
        if n == 0:
            return 0
        incl = max(A[0][0], A[1][0])
        excl = 0
        for i in range(1, n):
            new_excl = excl if excl > incl else incl
            incl = excl + max(A[0][i], A[1][i])
            excl = new_excl
        return excl if excl > incl else incl

Complexity

References