Max Sum Path in Matrix

Given an n x n integer matrix, your task is to find the maximum sum of a path which starts from the first row and ends at the last row. In each step, you select an element from the current row and move to the next row. When moving from one row to the next, you can choose an element from the same column, the column immediately to the left, or the column immediately to the right. Formally, if you choose column j in row i, then in row i+1 you may choose column j-1, j, or j+1 (if these indices are valid).

The result is the maximum sum obtainable following the above rules.

The transition can be formulated in LaTeX as follows:

\[ \text{dp}[i][j] = \max \begin{cases} dp[i-1][j-1] + matrix[i][j] & \text{if } j > 0,\\ dp[i-1][j] + matrix[i][j],\\ dp[i-1][j+1] + matrix[i][j] & \text{if } j < n-1. \end{cases} \]

inputFormat

The input is given via standard input (stdin) and has the following format:

 n
 row1_element1 row1_element2 ... row1_elementn
 row2_element1 row2_element2 ... row2_elementn
 ...
 rown_element1 rown_element2 ... rown_elementn

Where n is a positive integer representing the dimensions of the square matrix, followed by n lines of n integers each.

outputFormat

Output a single integer which is the maximum sum obtainable for a valid path according to the problem rules. The output should be printed to standard output (stdout).

3
1 2 3
4 5 6
7 8 9

18