你驾驶出租车行驶在一条有 n 个地点的路上。这 n 个地点从近到远编号为 1 到 n ，你想要从 1 开到 n ，通过接乘客订单盈利。你只能沿着编号递增的方向前进，不能改变方向。
乘客信息用一个下标从 0 开始的二维数组 rides 表示，其中 rides[i] = [starti, endi, tipi] 表示第 i 位乘客需要从地点 starti 前往 endi ，愿意支付 tipi 元的小费。
每一位 你选择接单的乘客 i ，你可以 盈利 endi - starti + tipi 元。你同时 最多 只能接一个订单。
给你 n 和 rides ，请你返回在最优接单方案下，你能盈利 最多 多少元。
注意：你可以在一个地点放下一位乘客，并在同一个地点接上另一位乘客。
思路：
每个ride可以选或者不选，求选的最大值，可以使用动态规划。
找到当前可以选的和上一个可以选的就可以写递推式。
dp[i]表示到第i个位置ride的最大值。
一共有n个位置，假设当前遍历到位置i，当前的选择：
以i为end的所有ride和不选。
如果选择以i为end的ride ，那么dp[i]=dp[ride.start] + ride.start - ride.end + tip;
如果第i个位置，不选，那么dp[i]=dp[i-1]
初始：dp[0]=0;
所以递推式：dp[i]=max( dp[i-1], dp[strart]+start-end+tip)
所以需要记录以每个位置结尾的ride。可以使用vector<vector<int>>来记录。
class Solution {
public:
long long maxTaxiEarnings(int n, vector<vector<int>>& rides) {
vector<vector<pair<int,int>>>end_list(n+1);
for(int i=0;i<rides.size();i++){
end_list[rides[i][1]].push_back({rides[i][0],rides[i][2]});
}
vector<long long>dp(n+1,0);
for(int i=1;i<=n;i++){
dp[i]=dp[i-1];
vector<pair<int,int>>v=end_list[i];
for(auto p:v){
dp[i]=max(dp[i],dp[p.first]+i-p.first+p.second);
}
}
return dp[n];
}
};