# Maximum sum path in a matrix

Given a square matrix of size N X N (1 <= N <= 1000) containing positive and negative integers with absolute value not larger than 1000, we need to compute the greatest sum achievable by walking a path, starting at any cell of the matrix and always moving downwards or rightwards. Additionally we also have to find the number of times that this sum is achievable.

For example:
For the matrix
1 1 1
2 2 2
3 3 3
The maximum sum is 12 and it occurs only once

• Hey, this is a standard dynamic programming exercise. What have you tried, and where are you stuck? See also Project Euler, Problem 18 — Maximum path sum I. – Pål GD May 28 at 11:56
• The since $N=O(1)$ and the absolute value of the integers is also upper bounded by a constant, this problem can be solved in time $O(1)$ by brute force. – Steven Jun 27 at 14:09

As Pal have commented, this is a question in dynamic programming. I will now propose the solution using dynamic programming to the question, but I highly recommend trying it on your own first, and checking this later.

The algorithm:

1. Create a new empty matrix $$V$$ of size N by N
2. for $$1 \le i \le N:$$
1. for $$1 \le j \le N:$$
1. Set $$V[i, j] = M[i,j] + max(V[i-1, j], V[i, j-1])$$ (note that $$V[-1,j] = V[i,-1] = 0$$)
3. Find $$m = max_i,_j(V[i,j])$$
4. Count the number of times we see $$m$$ in $$V$$
5. You can return the maximum sum $$m$$ and the number of times it occurs (as you have counted it)

Complexity:

The algorithm takes $$O(N^2)$$ time (which is $$O(k)$$ if we let $$k$$ be the input size) since it calculates a new matrix of size N by N, doing $$O(1)$$ operations per cell in it.

Notive that the algorithm's space complexity is also $$O(N^2)$$ as we were required to create a whole new matrix.