logo CodeStepByStep logo

Main Page → Exercises → Java → Solve an Exercise

deleteAndEarn

Language/Type: Java recursion recursive backtracking
Related Links:

Write a recursive method deleteAndEarn that accepts an array of integers and uses backtracking to find the maximum number of points that can be earned according to the following rules.

In each operation, you pick any element A[i] and delete it to earn A[i] points. Deleting said value will also cause the deletion of every element equal to exactly A[i] - 1 or A[i] + 1 without earning any additional points for doing so.

Here are some example calls to your method and their expected return values:

Array Return Explanation
[3, 4, 2] 6 Delete 4 to earn 4 points; 3 is also deleted. Then delete 2 to earn 2 points.
[2, 2, 3, 3, 3, 4] 9 Delete 3 to earn 3 points; both 2s and the 4 are also deleted. Then delete 3 again to earn 3 points. Then delete 3 again to earn 3 points.

You may assume that all values in the array are non-negative. Your method may alter the contents of the array as it executes, but it should be restored to its original state before your method returns.

Method: Write a Java method as described, not a complete program or class.

You must log in before you can solve this problem.

Log In

Need help?

Stuck on an exercise? Contact your TA or instructor.

If something seems wrong with our site, please

Is there a problem? Contact us.