Given an array of n integers named elements, we can perform several steps on the

ID: 3601449 • Letter: G

Question

Given an array of n integers named elements, we can perform several steps on the array. In each step, we choose an elementsi from the array and delete it to earn elementsi points; However, deleting elementsi also deletes any integers equal to elementsi + 1 and elementsi - 1 from elements. For exampls, if elements = [1,2,3,4], deleting 2 results in elements becoming [4] and earns us 2 points.

Compute a maxPoints function that has one parameter; an array of n integers named elements. The function must return a long integer denoting the maximum number of points we can earn by performing steps.

Constraints

1<= n <= 10 (to the power 5)

1 <= elements i <= 10 (to the power 5)

Sample Input : [3,4,2]
Output : 6

Explanation:
Given elements = [3,4,2], we maximize our score by performing the following steps:

Delete 4 to earn 4 points, which also deletes 4 - 1 = 3 and elements becomes [2].

Delete 2 to earn 2 points and elements become []

There are no more elements to delete, so we can't perform any more steps. The function returns the total number of points which is 4 + 2 = 6.

Explanation / Answer

import java.util.Arrays;

class Main {

    public static int maxPoints(int arr[]) {
        //Sort the array
        Arrays.sort(arr);
        //Now all our elements in the sorted order. So, the element[i]-1 and element[i]+1
        int n = arr.length;
        //dp[i] stores the answer for array starting at index i. dp[0] will be our answer
        int dp[] = new int[n + 1];
        //Ans for the last element is the element itself
        dp[n - 1] = arr[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            //If adjacent elements differ by 1, then check for 2 possibilities (Remove the current element or not )
            if(arr[i+1]-arr[i]==1){
                dp[i] = Math.max(dp[i + 1], arr[i] + dp[i + 2]);
            }
            else{
                //If adjacent elements do not differ by 1, we can remove both the elements and add it to the answer
                dp[i] = arr[i] + dp[i + 1];
            }
        }
        return dp[0];
    }

    public static void main(String[] args) {
        System.out.println(maxPoints(new int[]{3, 4, 2}));
    }
}

OUTPUT :

Navigate

Given an array of length 7 containing integers from 1 to 10,determine if it cont

Given an array of strings, write a function mostFrequentStrings(String[] in) usi

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

Given an array of n integers named elements, we can perform several steps on the

Question

Explanation / Answer

Related Questions

Navigate