Find the Maximum Number of Fruits Collected

Find the Maximum Number of Fruits Collected

What is this problem about?

The Find the Maximum Number of Fruits Collected coding problem presents a grid where three children start at different positions:

1. Child 1: Top-left corner $(0,0)$, moves only along the main diagonal to $(n-1, n-1)$.
2. Child 2: Top-right corner $(0, n-1)$, moves to $(n-1, n-1)$ using only moves that stay above the diagonal.
3. Child 3: Bottom-left corner $(n-1, 0)$, moves to $(n-1, n-1)$ using only moves that stay below the diagonal. You need to find the maximum total fruits collected by all three children.

Why is this asked in interviews?

Bloomberg uses this "Hard" problem to test your ability to decompose a complex problem into independent sub-problems. Since the paths of the three children are restricted to non-overlapping regions (diagonal, above-diagonal, below-diagonal), their collections are independent. It evaluation your mastery of Matrix Dynamic Programming and your ability to define valid movement rules.

Algorithmic pattern used

This is a Matrix Dynamic Programming problem.

1. Child 1: Path is fixed (the diagonal). Sum all grid[i][i].
2. Child 2 (Above): Use DP where dp[i][j] is the max fruits reaching cell $(i, j)$ from the top-right. Moves allowed are usually $(i-1, j-1), (i-1, j), (i-1, j+1)$.
3. Child 3 (Below): Use DP similarly for the bottom-left child.
4. Total = Sum(Diagonal) + DP_Above(n-1, n-1) + DP_Below(n-1, n-1).

Example explanation

Grid $3 imes 3$:

1. Child 1 collects (0,0), (1,1), (2,2).
2. Child 2 stays in the upper triangle (0,1), (0,2), (1,2).
3. Child 3 stays in the lower triangle (1,0), (2,0), (2,1). Since they never cross into each other's territory, we simply solve the "Max path in a triangle" DP twice and add the diagonal sum.

Common mistakes candidates make

• Overlap confusion: Thinking children can steal fruits from each other. The regions are strictly separated by the diagonal.
• Invalid moves: Forgetting the boundary conditions (e.g., Child 2 cannot move below the diagonal).
• Initialization: Not correctly setting the starting points for the two non-diagonal children.

Interview preparation tip

When you see multiple "actors" in a grid, check if their available moves allow them to ever visit the same cell. If not, the problem is just multiple independent DP problems combined at the end.