Maximum coins collected by travelling rows in a matrix

Question

input:

• a matrix of non-negative numbers.
• m rows, n columns.

process:

• start from the first row, select one column i and collect the coins there.
• move to the next row, select another column j, with cost |i-j|, and collect the coins.
• stop after the last row.

output:

• the maximum coins collected.

is there a O(mn) algorithm for this problem?

Answer 1

We are supposed to have a matrix[n][m] (n - rows, m - columns). Let's determine i_nj_m as a sum of a column starting from a i_nj_m coordinates in a matrix to the end of the matrix.
Let's introduce this statement as the first sum:
Σ₁ = i₁j₁ + i₁j₂ + i₁j₃ + _... + i₁j_m
So basically we are moving down the matrix and summing all the columns there for the Σ₁.
The next sums will be:
Σ₂ = i₁j₁ + i₁j₂ + i₁j₃ + _... + i₂j_m
Σ₃ = i₁j₁ + i₁j₂ + i₁j₃ + _... + i₃j_m
Σ₄ = i₁j₁ + i₁j₂ + i₁j₃ + _... + i₄j_m
And so on until we have
Σ_n = i₁j₁ + i₁j₂ + i₁j₃ + _... + i_nj_m
Now, we have to move to the next column by increasing the index of the previous element by 1 and returning to the index of 1 of the last:
Σ_n+1 = i₁j₁ + i₁j₂ + i₁j₃ + _... + i₂j_m-1 + i₁j_m
After that, it's obvious to continue like in the first steps:
Σ_n+2 = i₁j₁ + i₁j₂ + i₁j₃ + _... + i₂j_m-1 + i₂j_m
Σ_n+3 = i₁j₁ + i₁j₂ + i₁j₃ + _... + i₂j_m-1 + i₃j_m
Σ_n+4 = i₁j₁ + i₁j₂ + i₁j₃ + _... + i₂j_m-1 + i₄j_m
Comparing all the sums Σ (until you'll be on a i_nj_m) you will have the largest sum!

---

To use this algorithm it's good to have int matrix[n][m] to store all the coins inside,
int index[n][2] to store the indexes of the elements in the sums (n number of indexes for 2 elements), and int maxSum to store the largest sum.