-
Notifications
You must be signed in to change notification settings - Fork 1
/
Elite Day-28 Program-2.txt
57 lines (45 loc) · 1.21 KB
/
Elite Day-28 Program-2.txt
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
46
47
48
49
50
51
52
53
54
55
56
57
Ismart Shankar is given a set of N pluck cards, each card labelled
with a number on it, and he is also given a difference value as ‘D’.
Now Ismart Shankar has to find out the length of the largest arithmetic set ‘S’.
A subset is called as arithmetic set, iff the difference between
the numbers on any two adjacent cards is same as D.
A subset can be derived from the set of N pluck cads by deleting
some or no cards without changing the order of the remaining cards.
Input Format:
-------------
Line-1: Two space separated integers N, D, number of cards, difference.
Line-2: N space separated integers, numbers on the set of cards.
Output Format:
--------------
Print an integer, length of longest arithmetic subset.
Sample Input-1:
---------------
6 2
1 2 3 4 6 8
Sample Output-1:
----------------
4
Sample Input-2:
---------------
8 -2
8 1 2 6 5 4 2 0
Sample Output-2:
----------------
5
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,d;
cin>>n>>d;
vector<int> temp(n);
for(int i=0;i<n;i++){
cin>>temp[i];
}
map<int,int> m;
int ans=0;
for(int i=0;i<n;i++){
ans=max(ans,1+m[temp[i]-d]);
m[temp[i]]=m[temp[i]-d]+1;
}
cout<<ans<<endl;
}