Tic-tac-toe with only crosses
CJam (58 56 bytes)

2q~:Xm*{7Yb#W=}:F,Xm*{ee{~0a@*\+}%zS*F},_Wf%:z&amp;Mf*1fb:e&gt;


This is incredibly slow and uses a lot of memory, but that's code-golf for you.

Dissection

2q~:Xm*        e# Read input into X and find Cartesian product {0,1}^X
{7Yb#W=}:F,    e# Filter with a predicate F which rejects arrays with a 111
Xm*            e# Take the Cartesian product possible_rows^X to get possible grids
{              e# Filter out grids with an anti-diagonal 111 by...
  ee{~0a@*\+}% e#   prepending [0]*i to the ith row
  zS*F         e#   transposing, joining on a non-1, and applying F
},
_Wf%:z         e# Copy the filtered arrays and map a 90 degree rotation
&amp;              e# Intersect. The rotation maps horizontal to vertical and
               e# anti-diagonal to diagonal, so this gets down to valid grids
Mf*            e# Flatten each grid
1fb            e# Count its 1s
:e&gt;            e# Select the maximum


The number of valid rows is a tribonacci number and is \$\Theta(a^X)\$ where \$a\$ is the tribonacci constant, \$1.83928675\ldots\$. The number of grids generated in the Cartesian product is \$\Theta(a^{X^2})\$; the second filter will reduce the number somewhat, but the intersection is still probably \$\Theta(a^{X^4})\$.



An "efficient" approach ("merely" \$O(X a^{3X})\$) uses dynamic programming. Ungolfed in Java:

public class A181018 {
    public static void main(String[] args) {
        for (int i = 1; i &lt; 14; i++) {
            System.out.format("%d:\t%d\n", i, calc(i));
        }
    }

    private static int calc(int n) {
        if (n &lt; 0) throw new IllegalArgumentException("n");
        if (n &lt; 3) return n * n;

        // Dynamic programming approach: given two rows, we can enumerate the possible third row.
        // sc[i + rows.length * j] is the greatest score achievable with a board ending in rows[i], rows[j].
        int[] rows = buildRows(n);
        byte[] sc = new byte[rows.length * rows.length];
        for (int j = 0, k = 0; j &lt; rows.length; j++) {
            int qsc = Integer.bitCount(rows[j]);
            for (int i = 0; i &lt; rows.length; i++) sc[k++] = (byte)(qsc + Integer.bitCount(rows[i]));
        }

        int max = 0;
        for (int h = 2; h &lt; n; h++) {
            byte[] nsc = new byte[rows.length * rows.length];
            for (int i = 0; i &lt; rows.length; i++) {
                int p = rows[i];
                for (int j = 0; j &lt; rows.length; j++) {
                    int q = rows[j];
                    // The rows which follow p,q cannot intersect with a certain mask.
                    int mask = (p &amp; q) | ((p &lt;&lt; 2) &amp; (q &lt;&lt; 1)) | ((p &gt;&gt; 2) &amp; (q &gt;&gt; 1));
                    for (int k = 0; k &lt; rows.length; k++) {
                        int r = rows[k];
                        if ((r &amp; mask) != 0) continue;

                        int pqrsc = (sc[i + rows.length * j] &amp; 0xff) + Integer.bitCount(r);
                        int off = j + rows.length * k;
                        if (pqrsc &gt; nsc[off]) nsc[off] = (byte)pqrsc;
                        if (pqrsc &gt; max) max = pqrsc;
                    }
                }
            }

            sc = nsc;
        }

        return max;
    }

    private static int[] buildRows(int n) {
        // Array length is a tribonacci number.
        int c = 1;
        for (int a = 0, b = 1, i = 0; i &lt; n; i++) c = a + (a = b) + (b = c);

        int[] rows = new int[c];
        int i = 0, j = 1, val;
        while ((val = rows[i]) &lt; (1 &lt;&lt; (n - 1))) {
            if (val &gt; 0) rows[j++] = val * 2;
            if ((val &amp; 3) != 3) rows[j++] = val * 2 + 1;
            i++;
        }

        return rows;
    }
}