Maximum Profit Delivery Route
Shiprocket is constantly optimizing its delivery operations to enhance efficiency and profitability. Imagine a city represented as a grid, where each cell (i, j) corresponds to a potential package pickup location with an associated profit. A delivery agent needs to navigate this grid, starting from the top-left corner and reaching the bottom-right corner, collecting packages along their path to maximize total profit.
Your task is to implement a function getMaxProfit that calculates the maximum total profit a delivery agent can collect. The agent starts at the top-left corner (0, 0) and must reach the bottom-right corner (M-1, N-1). At each step, the agent can only move either right or down. Some cells might be blocked (obstacles), meaning the agent cannot enter or pass through them.
profits: A 2D array (matrix) of integers M x N. profits[i][j] represents the profit obtainable from cell (i, j).
profits[i][j] >= 0, it's a valid location with the specified profit.profits[i][j] == -1, it signifies an obstacle, and the agent cannot enter this cell.(0, 0) to (M-1, N-1).(0, 0) or (M-1, N-1) is an obstacle, or if no valid path exists to the destination, return -1.(0, 0) or the end cell (M-1, N-1) is marked as an obstacle (-1), no valid path can exist, and the function should return -1.M >= 1, N >= 1).Examples
Example 1
Input:
profits = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
Output:
29
Note:
The path (0,0) -> (1,0) -> (2,0) -> (2,1) -> (2,2) yields 1 + 4 + 7 + 8 + 9 = 29, which is the maximum profit.
Example 2
Input:
profits = [[1, 10, -1], [1, -1, 5], [1, 1, 100]]
Output:
104
Note:
Cells (0,2) and (1,1) are obstacles. The only valid path is (0,0) -> (1,0) -> (2,0) -> (2,1) -> (2,2), yielding 1 + 1 + 1 + 1 + 100 = 104.
Example 3
Input:
profits = [[1, -1], [-1, 10]]
Output:
-1
Note:
Cells (0,1) and (1,0) are obstacles, making it impossible to reach (1,1) from (0,0). Thus, no valid path exists.
Example 4
Input:
profits = [[-1]]
Output:
-1
Note:
The start cell (0,0) is an obstacle, so no path is possible.
Constraints
1 <= M, N <= 200 (where M is the number of rows, N is the number of columns)-1 <= profits[i][j] <= 1000O(M * N).O(M * N) or O(N) (optimized).Loading editor...