simple java solution beats 98% using Map O(n) solution
please upvote if you like the solution \ntime-O(n)\nspace-O(n)\n\nclass Solution {\n    public long maxTaxiEarnings(int n, int[][] a) {\n        Map<Integer,Lis
please upvote if you like the solution \ntime-O(n)\nspace-O(n)\n```\nclass Solution {\n    public long maxTaxiEarnings(int n, int[][] a) {\n        Map<Integer,List<pair>> map = new HashMap<>();\n        long dp[]=new long [n+1];\n        for(int x[]:a){\n            if(!map.containsKey(x[1]))map.put(x[1],new ArrayList<>());\n            map.get(x[1]).add(new pair(x[0],x[2]));\n        }\n        for(int i=1;i<=n;i++){\n            if(map.containsKey(i)){\n                for(pair x:map.get(i)){\n                    long cur=i-x.s+x.val;\n                    dp[i]=Math.max(cur+dp[x.s],dp[i]);\n                    dp[i]=Math.max(dp[i],dp[i-1]);\n                }\n            }else dp[i]= dp[i-1];\n        }\n        \n        return dp[n];\n    }\n}\nclass pair{\n    int s,val;\n    pair(int s,int val){\n        this.s=s;\n        this.val=val;\n    }\n}\n```
['Dynamic Programming', 'Java']