Worked out a Dynamic Programming Approach to the problem –

int t[n][2]; //Stores grid values
int b[n]; //Stores best solution upto a particular column
b[0]= t[0][1]-t[0][0]; //Compute score for first column (Absolute Value)
b[1]= Max (b[0] + Score for column 1 vertically, Score for first 2 horizontal columns);
for i=0...n 
  b[i]= Max ( b[i-1] + Score for column i vertically, b[i-2] + Score for horizontal columns i & i-1);
print b[n-1];

Works efficiently on the given data set, with a linear time complexity!

Here is one way to approach/describe the problem:

When looking at the 2xN grid, you can see that any tiling is uniquely defined in the following way:

For the most left block, see if it is horizontal or vertical. Then look at the next block.

Suppose 2 stands for horizontal and 1 stands for vertical your Tiling 1 can be written as: 121
whilst Tiling 2 can be written as 22

Given each vector, calculating the total cost should be straightforward.

Now you can use this algorithm:

1. Find a starting position (probably your own algorithm can do the trick here)
2. Given a window length (say 5) try all combinations of ones and zeros within the window and calculate what the maximum improvement is.
3. Optional: Execute this improvement
4. Shift the window, so instead of looking at the first 5 odd columns now look at odd column 2 to 6
5. If you are not yet at the end, go to step 2, else execute the improvement.
6. Optional: If you found any improvements, you can go to step 1

Here’s C++ implementation in O(n) :

Using dynamic programming, we are building from the bottom-up, the best solution for each and every column.

Base cases are column 0 and 1 :

Best[0] => The score for mini tiles of column 0

Best[1] => The maximum out of 2 possible solutions set!
(1. Row wise pairing and
2. column wise pairing)

Otherwise :

Best[n] => The maximum out of 2 possible solutions set again
(1. The sum of new column and the older best solution B[n-1]
2. The sum of older best solution B[n-2] and the new 2×2 tile square formed)

#include<iostream> 
using namespace std;
int abs(int n) { if(n < 0) return -1*n ; else return n; }

int main()
{
    int n, A[100001][2], B[100001], i, j;
    cin>>n;
    for(i=0;i<2;i++)
    {
        for(j=0;j<n;j++)
            cin>>A[j][i];
    }

    B[0] = abs(A[0][0] - A[0][1]);
    B[1] = max( B[0] + abs(A[1][0]-A[1][1]) , abs(A[1][0]-A[0][0])+abs(A[1][1]-A[0][1]) );
    for(i=2;i<n;i++)
        B[i] = max( B[i-1] + abs(A[i][0]-A[i][1]) , B[i-2] + abs(A[i][0]-A[i-1][0]) + abs(A[i][1]-A[i-1][1]) );

    cout<<B[n-1]<<endl;
    return 0;
}