Matrix Traversal
Flexport● EasyFULLTIMEOAProblem statement
Given a 4 x 4 matrix mat, the initial energy is 100. The task is to reach the last row of the matrix with the maximum possible energy left.
The matrix can be traversed in the following way:
- Start with any cell in the first row.
- In each move, traverse from cell (i, j) of the ith row and jth column to any existing cell out of (i + 1, j - 1), (i + 1, j), or (i + 1, j + 1).
- Finish the traversal in the last row.
After stepping on a cell (i, j), energy decreases by mat[i][j] units. Find the maximum possible energy left at the end of the traversal.
Note: The final energy can be negative.
Function
maxEnergy(mat: int[][]) → int
Complete the function maxEnergy in the editor below.
maxEnergy has the following parameter:
int mat[4][4]: a matrix of integers
Returns int: the maximum possible energy at the end of the traversal
Examples
Example 1
mat = [[10, 20, 30, 40], [60, 50, 20, 80], [10, 10, 10, 10], [60, 50, 60, 50]]return = 0Possible paths (0-based indexing is used):
- (0, 0) - (1, 1) - (2, 2) - (3, 3)
- (0, 1) - (1, 2) - (2, 2) - (3, 2)
For the first path, energy left = 100 - 10 - 50 - 10 - 50 = -20 For the second path, energy left = 100 - 20 - 20 - 10 - 50 = 0 It can be proven that 0 is the maximum energy possible at the end of the traversal so return 0.
Constraints
0 <= mat[i][j] < 100