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.
