Maximizing the sum of selected elements in a matrix
The problem you want to solve is (a slight variation of) maximum weighted matching in general (i.e., not necessarily bipartite) graphs.  There are several algorithms with various worst-case bounds:


"Data structures for weighted matching and nearest common ancestors with linking" (Gabow 1990) is the best "in theory" with $O(nm + n^2\log n)$ time complexity.
"Faster scaling algorithms for general graph-matching problems" (Gabow and Tarjan 1991) has time complexity $O(m\log(nN)\sqrt{n\alpha(n, m)\log n})$, where $N$ is the largest cost value and $\alpha(n, m)$ is the very slow-growing "inverse Ackermann" function.
"Computing minimum-weight perfect matchings" (Cooke and Rohe 1999) describes the "Blossom IV" algorithm, which apparently performs well in practice despite a theoretical worst case $O(n^3)$ time.  The paper also gives a good overview of existing algorithms.
"Implementation of $O(nm\log n)$ weighted matchings in general graphs: the power of data structures" (Mehlhorn and Schäfer 2002) apparently performs even better in most cases, and also comes with a better worst-case guarantee.  There is an implementation in LEDA.
"Blossom V: A new implementation of a minimum cost perfect matching algorithm" (Kolmogorov 2009) claims to outperform the previous algorithm a majority of the time.


The above algorithms don't allow "self-edges" (choosing elements along the diagonal).  To accommodate these, for every vertex $v_i$, create an extra vertex $u_i$, and an edge $(v_i, u_i)$ with weight $a_{ii}$.

Note that while some of these papers talk about the maximum weight perfect matching problem, in which we have the additional constraint that every vertex must be incident on an edge in the matching, you can turn any instance of the plain maximum weight matching problem into an instance of the perfect kind by adding, for every existing vertex $v_i$, a new vertex $v'_i$, a zero-cost edge $(v_i, v'_i)$, and another zero-cost edge between every pair ($v'_i, v'_j)$ of new vertices.  (Perhaps another construction using fewer zero-weight edges is possible?)

I found most of the above information in https://people.mpi-inf.mpg.de/~mehlhorn/ftp/WeightedMatchings.pdf, which has a lot of useful information on implementation and theory.