C++ | O(N) | Easy to Understand
Runtime: 537 ms, faster than 96.31% of C++ online submissions for Maximum Earnings From Taxi.\nMemory Usage: 122.5 MB, less than 30.66% of C++ online submission
Runtime: 537 ms, faster than 96.31% of C++ online submissions for Maximum Earnings From Taxi.\nMemory Usage: 122.5 MB, less than 30.66% of C++ online submissions for Maximum Earnings From Taxi.\n\n\n```\nclass Solution {\npublic:\n    long long maxTaxiEarnings(int n, vector<vector<int>>& rides) {\n        vector<pair<int,int>> roads[n+1];\n        for(vector<int> v: rides) {\n            roads[v[1]].push_back({v[0], v[1]-v[0]+v[2]});\n        }\n        long long dp[n+1];\n        memset(dp, 0, sizeof(dp));\n        for(int i=2; i<=n; i++) {\n              dp[i] = dp[i-1];\n              for(auto j: roads[i]) {\n                dp[i] = max(dp[i], j.second + dp[j.first]);\n              }\n           }\n        return dp[n];\n    }\n};\n```
['Dynamic Programming', 'Graph']