City Tour — Maximise Profit Tech Mahindra - IIT (ISM) Dhanbad

Problem Preview

"**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."