Morgan Stanley OA-4 2022

Problem Description

An online taxi service is facing losses due to recent changes in its discount prices. To address the issue, the team has created a list of M places in a city with N routes between them. Each route has three components:

1. The pickup position ID.
2. The destination position ID.
3. The cost per trip between the pickup and destination.

• If the cost is positive, the company makes a profit from that trip.
• If the cost is negative, the company incurs a loss from that trip.
• If the pickup and destination are the same, the trip is considered a round trip.

The company wants to calculate the maximum loss incurred from any round trip. Your task is to write an algorithm that finds the maximum amount of money the company is losing in any round trip.

Input Format

• The first line contains two integers M and N, representing the number of places and the number of routes, respectively.
• The next N lines each contain three integers:
  • pickupID — the ID of the pickup position.
  • destinationID — the ID of the destination position.
  • cost — the cost per trip between the pickup and destination.

Output Format

• Print a single integer representing the maximum loss from a round trip.

Constraints

• 1 <= totalRoutes <= 10^4
• 0 <= pickupID, destinationID <= 10^4
• -10^3 <= cost <=10^3

Sample Input

4 5
0 1 -1
1 2 -2
2 0 -5
0 3 6
3 2 3

Sample Output

-8

Explanation

In this case, the following round trips incur losses:

• Round trip at node 0 (travel from 0 → 0): total loss of -8.
• Round trip at node 1 and 2 also result in losses, but the loss at node 0 is the maximum at -8.

Hence, the output is -8.