This answer is a modification of the algorithm for the "Unique Paths" problem I wrote here: Trying to solve the “Unique Paths” problem, but getting the wrong answer. That other challenge had the same constraint, you can only move down and right, which is why a similar algorithm works.
In this case, we can start at the top-left. We need to maintain 2 arrays, one for the sum achievable for a given cell, and one for the count of paths to get that sum. We also need two variables for the highest sum/count achievable overall (maxSum and maxCount). All of these are initialized to 0's.
For each cell, there are 3 "paths" leading here, and we calculate what the sum/count would be for each of those paths (if possible), where row is an array of the matrix values for the current row being processed:
From above:
The sum/count values are currently the accumulated values from the previous row. Since sum/count values were initialized to 0's, they can be used even when processing the first row.
sumAbove = sum[col] + row[col]
countAbove = count[col]
From the left:
The sum/count values are currently the accumulated values from the previous cell of the current row, because we just updated that when iterating from left to right.
sumLeft = sum[col - 1] + row[col] or row[col] if col == 0
countLeft = count[col - 1] or 0 if col == 0
Starting here:
sumStart = row[col]
countStart = 1
We then find the highest sum of the three, and set the new sum[col] to that value. The new count[col] value will be the sum of the counts where the sum is the max, e.g. if all 3 sums are the same, then count[col] = countAbove + countLeft + countStart.
If the new sum[col] is higher than maxSum, then we update maxSum/maxCount to these new values. If the new sum[col] equals maxSum, we add the new count[col] to maxCount.
Let us use the following matrix as an example:
3 1 -4 1 3
-6 -1 4 -1 -4
1 1 1 1 1
-1 2 2 1 1
12 -5 1 1 0
We start with all 0's.
sum = { 0, 0, 0, 0, 0 }, count = { 0, 0, 0, 0, 0 }, maxSum = 0, maxCount = 0
Process the first row:
row: { 3, 1, -4, 1, 3 }
bestPath: { start, left, left, left/start, left }
sum = { 3, 4, 0, 1, 4 }, count = { 1, 1, 1, 2, 2 }, maxSum = 4, maxCount = 2
For the first three, there is one path to get those sums, i.e. starting at 0,0. For the last two, there are two paths to get those sums, i.e. starting at 0,0 or 3,0 (col,row). To clarify that, we showed the which path lead to the new values labeled bestPath.
Process the second row:
row: { -6, -1, 4, -1, -4 }
bestPath: { above, above, left, left, left }
sum = { -3, 3, 7, 6, 2 }, count = { 1, 1, 1, 1, 1 }, maxSum = 7, maxCount = 1
Process the third row:
row: { 1, 1, 1, 1, 1 }
bestPath: { start, above, above, above, above }
sum = { 1, 4, 8, 7, 3 }, count = { 1, 1, 1, 1, 1 }, maxSum = 8, maxCount = 1
Process the fourth row:
row: { -1, 2, 2, 1, 1 }
bestPath: { above, above, above, left, left }
sum = { 0, 6, 10, 11, 12 }, count = { 1, 1, 1, 1, 1 }, maxSum = 12, maxCount = 1
Process the fifth row:
row: { 12, -5, 1, 1, 0 }
bestPath: { start/above, left, above, above/left, above/left }
sum = { 12, 7, 11, 12, 12 }, count = { 2, 2, 1, 2, 3 }, maxSum = 12, maxCount = 9
Final result:
12 9
With an N x N matrix, this code has excellent O(m) time complexity, where m = N², i.e. the number of cells in the matrix, and O(N) aka O(sqrt m) storage complexity.
