Mode: On-Campus Exam Pattern: 3 coding question OA Date: 2026-10-14

City Tour — Maximise Profit

Topic: Dynamic Programming, Grid Paths, Round-Trip Optimization

You work as a driver for ABC Tours. You start at a particular location in a city, travel to a destination, and then return to your starting point. Your objective is to maximize the total profit earned by picking up customers along the way.

The city is represented by an grid. Each cell contains one of the following values:

• 0: No customer.

• -1: A blocked road that cannot be crossed.

• A positive integer x: A customer who pays x.

The starting point is the top-left cell , and the destination is the bottom-right cell .

Outward journey

Starting from , travel to . You can move only:

• Right:

• Down:

You cannot pass through blocked cells.

Whenever you collect a customer, you earn the amount in that cell. Once collected, the customer is removed, and the cell becomes 0.

Return journey

Travel back from the destination to the starting point. You can move only left or up, and you cannot pass through blocked cells.

Customers already collected during the outward journey cannot be counted again.

Task

Implement maximiseProfit to return the maximum total profit earned over both journeys. If a complete outward and return journey is impossible, return 0.

Function signature

java public int maximiseProfit( int input1, int input2, int[][] input3 )

Example 1

Input:

text input1 = 3 input2 = 3

input3 = [ [ 0, 2, 3], [-1, 1, 1], [ 6, 1, 2] ]

Output:

text 10

The optimal round trip collects customers without counting any customer twice.

Example 2

Input:

text input1 = 4 input2 = 2

input3 = [ [ 5, 0], [-1, 9], [ 3, -1], [10, 10] ]

Output:

text 0

The blocked roads prevent a complete journey, so the answer is 0.