Пусть $$$a'_i$$$ — последовательность чисел из $$$a_i$$$, упорядоченных по невозрастанию. Для матрицы размера $$$k \times k$$$ максимальный след можно получить взяв $$$a'_1, a'_2, \dots a'_k$$$. При этом, если $$$a'_k < 0$$$, то максимальный след матрицы размера $$$k-1 \times k-1$$$ будет больше. А если $$$a'_{k+1} > 0$$$, то выгоднее взять матрицу размера $$$k+1 \times k+1$$$.
Таким образом, выгодно взять максимальное $$$k$$$, такое что $$$k \le \sqrt{n}$$$ и $$$a'_k \ge 0$$$. Если же $$$a'_1 < 0$$$, то $$$k=1$$$ и след будет меньше нуля.