select and delete


  • 0
    S

    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 elements i points; However, deleting elements i also deletes any integers equal to elements i + 1 and elements i - 1 from elements. For exampls, if elements = [1,2,3,4], deleting 2 results in elements becoming [4] and earns us 2 points.

    Compute the 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.


  • 0
    H

    The code is very simple as explained by smallsong, we only need to consider the values behind and not the ones ahead. so the below code should give out correct answer.

    '''
    import java.awt.List;
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.Collections;
    import java.util.HashMap;
    import java.util.Map;
    import java.util.Scanner;

    public class PocketGems {

    public static void main(String[] args) {
    	int quit = 0;
    	int[] val=new int[]{7,5,3,4,4,6};
    	calc(val);
    	
    
    }
    
    private static void calc(int[] val) {
    	Map<Integer,Integer> map = new HashMap();
    	Arrays.sort(val);
        ArrayList<Integer> keys = new ArrayList();
    	for(int i =0; i < val.length; i++)
    	{
    		if(map.containsKey(val[i]))
    		{
    			int x = map.get(val[i]);
    			map.remove(i);
    			map.put(val[i],++x);
    		}
    		else
    		{   
    			map.put(val[i],1);
    			keys.add(val[i]);
    		}
    		
    	}
    	System.out.println("Values and their occurences numbers are "+ map);
    	
    	Collections.sort(keys);
    	int dp[] = new int[keys.size()];
    	
    	dp[0] = map.get(keys.get(0))*keys.get(0);
    	
    	if(keys.get(1)==keys.get(0)+1)
    	  dp[1] = Math.max(dp[0],map.get(keys.get(1))*keys.get(1));
    	else
    	  dp[1] = dp[0] + map.get(keys.get(1))*keys.get(1);
    	
    	int max = Math.max(dp[0],dp[1]);
    	
    	System.out.println("Unique keys in order" + keys);
    	
    	for(int i =2 ; i < keys.size(); i++)
    	{  
    		int temp = keys.get(i);
    		
    		if(keys.get(i)==keys.get(i-1)+1)
    		  dp[i] = Math.max(dp[i-1],(dp[i-2]+ temp *map.get(temp)));
    		else
    		  dp[i] = dp[i-1]+ temp *map.get(temp);
    		
    		if(dp[i]> max)
    		{
    			max = dp[i];
    		}
    		
    	}
    	
    	System.out.println(max);
    	
    }
    

    }

    '''


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.