one way is two for
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 | public static int getMaxProfit(int M, int[] profit, int[] city, int[] visit){ int len = visit.length; int sum = 0; int maxPossible=0; int maxCitiIndex=0; for (int i = 0; i < len; i++) { // find visitable array. boolean find = false; for(int j=0; j<city.length; j++){ if(visit[i] == city[j]){ if(maxPossible < profit[j]){ maxPossible = profit[j]; maxCitiIndex =j; find = true; } } } if(find){ profit[maxCitiIndex] = 0; sum+= maxPossible; } maxPossible=0; maxCitiIndex=0; } return sum; } |
and the other is
make List array and reversOrder
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | public static int getMaxProfit(int M, int[] profit, int[] city, int[] visit){ ArrayList<Integer>[] list = new ArrayList[M+1]; int max = 0; for (int i = 0; i < list.length; i++) { list[i] = new ArrayList<Integer>(); } for (int i = 0; i < city.length; i++) { list[city[i]].add(profit[i]); } for (int i = 0; i < list.length; i++) { Collections.sort(list[i], Collections.reverseOrder()); } for (int i = 0; i < visit.length; i++) { if(list[visit[i]].size() > 0){ Integer x = list[visit[i]].remove(0); max += x; } } return max; } |
No comments:
Post a Comment