How should I practice Maximum Falling Path Sum?

Start by reading the full statement, solve the visible examples, then compare the pattern against related IMC Trading phone screen problems in FastPrep.

Is Maximum Falling Path Sum associated with IMC Trading?

FastPrep tags this as a IMC Trading phone screen coding practice problem when the problem catalog has that company and stage context.

Maximum Falling Path Sum

IMC Trading● MediumNEW GRADPHONE SCREEN

Learn

Problem statement

You are given an n-by-m integer matrix. A falling path starts at any cell in the first row and must finish in the last row.

From (row, col), move to exactly one cell in the next row: (row + 1, col - 1), (row + 1, col), or (row + 1, col + 1). Every visited cell must remain inside the matrix.

The path sum includes every visited value, including both endpoints. Return the maximum possible sum. A path contains exactly one cell from every row.

Function

maxFallingPathSum(matrix: int[][]) → int

Examples

Example 1

matrix = [[10,10,2,0,20,4],[1,0,0,30,2,5],[0,10,4,0,2,0],[1,0,2,20,0,4]]return = 74

A path with values 20, 30, 4, 20 has sum 74.

Example 2

matrix = [[1,2,3],[9,8,7],[4,5,6]]return = 17

The path 3, 8, 6 reaches the last row with sum 17.

Example 3

matrix = [[-5,-2],[-4,-3]]return = -5

The best complete path is -2, -3. Stopping at the first row is not allowed.

Example 4

matrix = [[4],[-9],[2]]return = -3

The only column forces the path 4, -9, 2, whose sum is -3.

Constraints

For this exercise, assume 1 <= n, m <= 200.
For this exercise, assume -10^6 <= matrix[row][col] <= 10^6.
Every row contains exactly m values.
The maximum absolute path sum is at most 2 * 10^8, which fits in a signed 32-bit integer.