# Maximum sum of values in a square grid (one in each row/ column)

this is my first post here so bare with me :).

What i'm looking for is an algorithm that can find the maximum sum of values in a square grid under the restriction, that you can only pick 1 value from each column and row.

so for example:

$$\begin{matrix} 3 & 2 & 5 \\ 4 & 1 & 4 \\ 3 & 1 & 2 \\ \end{matrix}$$

in the first row, you pick 5, in the second you pick 4 and in the third you pick 1, for a total of 5+4+1 = 10.

The algorithm I came up with is similar to using Laplace expansion to find the determinant of a matrix.

(I'm using matrix and square grid interchangebly)

For every value in the first row, you recursively find the max sum of the matrix without that values' column/row and then add that result with the value. The maximum of these is our result (recursion end: 1x1 matrices return the value).

This algorithm runs in O(n!) (T(n) = n*T(n-1) for n x n square grids) and I was wondering if anyone of you can come up with a faster algorithm.

I know that there are faster algorithms for finding the determinant, such as LU decomposition O(n^3) and Bareiss' algorithm O(n^3) or fast matrix multiplication O(n^2.373), but the ones I have looked at were to confusing for me to change into a fitting algorithm for this problem.