Easy DP - Explained - O(n)
Please upvote if you find the solution helpful :) Thanks!\n\n\n# Approach 1: DP\n# Time:  O(n)\n# Space: O(n)\n\n# Intuition: \n# We want to loop from location 
# Please upvote if you find the solution helpful :) Thanks!\n\n```\n# Approach 1: DP\n# Time:  O(n)\n# Space: O(n)\n\n# Intuition: \n# We want to loop from location = 1 to n and at each step check if this location is an end point or not .\n# If it is an end point then we check all of its corresponding start points and get the maximum fare we can earn .\n# In order to quickly check if this number is an end point or not maintain a hashmap where keys="end point" and the values="[start_point, tip]""\n\ndef maxTaxiEarnings(n, rides):\n    """\n    :type n: int\n    :type rides: List[List[int]]\n    :rtype: int\n    """\n    import collections\n    hashmap = collections.defaultdict(list)\n    for start, end, tip in rides:\n        hashmap[end].append((start, tip))\n\n    dp = [0]*(n+1)\n    for location in range(1, n+1):\n        # taxi driver has the fare from the previous location, let\'s see if he/she can make more money by dropping someone at the current location\n        # we check that by checking if the current location is an end point, among the ones gathered as hashmap keys\n        dp[location] = dp[location-1] \n        if location in hashmap:\n            profitDroppingPassengersHere = 0\n            # for each ending trip at the current \'location\'\n            for start, tip in hashmap[location]:\n                profitDroppingPassengersHere = max(profitDroppingPassengersHere, location - start + tip + dp[start])\n            # update the dp\n            dp[location] = max(dp[location], profitDroppingPassengersHere)\n\n    return dp[n]\n```
['Dynamic Programming', 'Python']