So the longest subway ride in NYC is 24km (15 miles) and 1h long? We have multiple underground lines farther than this in Berlin with the longest being 32km (20 miles). But don't get fooled, the issues are the same.

Is this like the travelling salesman problem, but looking for the longest, not shortest journey?

The longest route on the NYC subway is precisely when you have an appointment and the train decides to stop because there's electrical issues, someone jumped on the track, "there's a train stopped ahead of us", the express decides to go local instead, someone is holding the door, your route involves the F/G or any line that serves less affluent neighborhoods...