-
Notifications
You must be signed in to change notification settings - Fork 0
/
Boredom
45 lines (36 loc) · 1.2 KB
/
Boredom
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
35
36
37
38
39
40
41
42
43
44
45
Boredom
Send Feedback
Gary is bored and wants to play an interesting but tough game . So he figured out a new board game called "destroy the neighbours" . In this game there are N integers on a board. In one move, he can pick any integer x from the board and then all the integers with value x+1 or x-1 gets destroyed .This move will give him x points.
He plays the game until the board becomes empty . But as he want show this game to his friend Steven, he wants to learn techniques to maximise the points to show off . Can you help Gary in finding out the maximum points he receive grab from the game ?
Input Format :
Line 1 : Integer N
Line 2 : A list of N integers
Output Format :
Maximum points Gary can recieve from the Game setup
Constraints :
1<=N<=10^5
1<=A[i]<=1000
Sample Input :
2
1 2
Sample Output :
2
public class solution {
public int solve(int n,int arr[])
{
int freq[]=new int[1001];
for(int i=0;i<n;i++)
{
freq[arr[i]]++;
}
int dp[]=new int[1001];
dp[1]=freq[1];
for(int i=2;i<=1000;i++)
{
int m1=dp[i-1];
int m2=dp[i-2]+freq[i]*i;
dp[i] = Math.max(m1,m2);
}
return dp[1000];
}
}