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

  • 3
    $\begingroup$ 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. $\endgroup$ – Pål GD May 28 '20 at 11:56
  • $\begingroup$ 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. $\endgroup$ – Steven Jun 27 '20 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)


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.