按照要求保留数组元素使得和最大

Description

Given an array of N numbers, we need to maximize the sum of selected numbers. At each step, you need to select a number Ai, delete one occurrence of Ai-1 (if exists) and Ai each from the array. Repeat these steps until the array gets empty. The problem is to maximize the sum of selected numbers.

给定一个N个数的数组，我们需要最大化所选数的和。在每个步骤中，您需要从数组中选择一个数字Ai，删除一个Ai-1(如果存在)和Ai。重复这些步骤，直到数组为空。问题是使所选数字的和最大化。

Input

The first line of the input contains T denoting the number of the test cases. For each test case, the first line contains an integer n denoting the size of the array. Next line contains n space separated integers denoting the elements of the array.
Constraints:1<=T<=100，1<=n<=50，1<=A[i]<=20
Note: Numbers need to be selected from maximum to minimum.

输入的第一行包含T，表示测试用例的数量。对于每个测试用例，第一行包含一个整数n，表示数组的大小。下一行包含n个用空格分隔的整数，表示数组的元素。
约束:1 < = T < = 100, 1 < = n < = 50, 1 < =[我]< = 20
注意:数字需要从最大值选择到最小值。

Output

For each test case, the output is an integer displaying the maximum sum of selected numbers.

对于每个测试用例，输出是一个整数，显示所选数字的最大和。

Sample Input

2
3
1 2 3
6
1 2 2 2 3 4

Sample Output

4
10

Solution

public class DeleteAiMinusOneGetMaxSum {

    public static void main (String[] args) {
        Scanner in = new Scanner(System.in);
        int caseNum = in.nextInt();
        for(int i = 0; i < caseNum; i++){
            int arrLen = in.nextInt();
            ArrayList<Integer> arr = new ArrayList<Integer>();
            for(int j = 0; j < arrLen; j++){
                arr.add(in.nextInt());
            }
            System.out.println(deleteAiMinusOneGetMaxSum(arr));
        }
    }

    public static int deleteAiMinusOneGetMaxSum(ArrayList<Integer> arr){
        Collections.reverse(arr);
        int sum = 0;
        while(!arr.isEmpty()){
            int num = arr.get(0);
            sum += num;
            arr.remove(0);
            if(arr.indexOf(num - 1) >= 0){
                arr.remove(arr.indexOf(num - 1));
            }
        }
        return sum;
    }
}