SUBJECT-ARRAY N DISTINCT ELEMENTS - APOC2_02 - EDITORIAL
PROBLEM LINK
Author: codechefsrm
Editorialist : codechefsrm
DIFFICULTY
EASY-MEDIUM
PREREQUISITES
Arrays,Sets
PROBLEM
Chef is multitalented but he mistakenly took part in 2 contest which will take place at the same time. So while chef is busy at one cooking contest,
he wants you to take part in coding contest.
Chef wants u to solve this program for him.
You have been given an array of size n. You have to calculate a subarray of size k with maximum sum having distinct elements same as original array.
EXPLANATION
Given the constrains we can apply brute force solution here.
First we create a set and find the unique elements in our given array.
We can loop for each subarray for size K and add them in the set , if our set has the same size as that of the initial set then it is a possible
candidate for our answer.
We can find the maximum of all these possible answers and print our answer.
Program
Setter's Solution
#include<bits/stdc++.h>
#define ll long long int
#define pb push_back
#define vi vector
#define repi(x,n) for(ll i=x;i<n;++i)
#define repj(x,n) for(ll j=x;j<n;++j)
#define input(x) cin>>x
#define print(x) cout<<x<<‘\n’
#define endl ‘\n’
using namespace std;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t;
cin>>t;
while(t–)
{
sets;
ll n,k;
cin>>n>>k;
vi v;
repi(0,n)
{
ll a;
cin>>a;
s.insert(a);
v.pb(a);
}
ll ans=0;
ll su=0;
ll sz=s.size();
repi(0,n)
{
if(i<=n-k)
{
su=0;
sets1;
repj(i,i+k)
{
s1.insert(v[j]);
su+=v[j];
}
if(s1.size()==sz)
{
ans=max(ans,su);
}
s1.clear();
}
}
print(ans);
}
return 0;
}