C++ | TOP DOWN DP | BINARY SEARCH
class Solution {\npublic:\n    vector dp ; \n    \n \n    long long helper(int i , vector> &rides )\n    {\n        if(i==rides.size())\n            return 0 ;\
class Solution {\npublic:\n    vector<long long> dp ; \n    \n \n    long long helper(int i , vector<vector<int>> &rides )\n    {\n        if(i==rides.size())\n            return 0 ;\n       \n        if(dp[i]!=-1)\n            return dp[i] ;\n        \n        int s = i+1 , e = rides.size() -1 ;\n        int ans  = -1; \n        \n        while(s<=e)\n        {\n            int mid = (s+e)/2 ;\n            \n            if(rides[mid][0] >= rides[i][1])\n            {\n                ans = mid ;\n                e=mid-1;\n            }\n            else\n            s = mid+1 ; \n            \n        }\n  \n        \n        long long ans1  = rides[i][1] - rides[i][0] + rides[i][2]  ;\n        \n        if(ans != -1)\n            ans1 += helper(ans , rides); \n        \n        \n        return dp[i] = max(ans1 , helper(i+1 , rides )) ; \n        \n    }\n    long long maxTaxiEarnings(int n, vector<vector<int>>& rides) {\n        \n        \n        sort(rides.begin() , rides.end()) ;\n        \n        dp.resize(rides.size() , -1) ;\n        \n        return helper(0 , rides ) ; \n        \n    }\n};
[]