# Maximize the sum | Hackerearth practice problem solution

Problem:-

You are given an array

$A$

of

$N$

integers. You want to choose some integers from the array subject to the condition that the number of distinct integers chosen should not exceed

$K$

You are given

$T$

test cases.

Input format

• The first line contains a single integer
$T$

denoting the number of test cases.

• The first line of each test case contains two space-separated integers
$N$

and

$K$

denoting the length of the array and the maximum number of distinct integers you can choose.

• The second line of each test case contains
$N$

space-separated integers denoting the integer array

$A$

.

Output format

For each test case(in a separate line), print the maximum sum you can obtain by choosing some elements such that the number of distinct integers chosen is at most

$K$

. If you cannot choose any element, output

$0$

.

Constraints

Sample Input
`24 13 -1 2 54 22 1 2 5`
Sample Output
`59`
Time Limit: 1.5
Memory Limit: 256
Source Limit:
Explanation

In the first test case, we have

$N=4,K=1$

$A=\left[3,-1,2,5\right]$

. Since we can choose atmost 1 distinct integer, we choose

$5$

. The sum is also

$5$

and we output it.

In the second test case, we have

$N=4,K=2$

$A=\left[2,1,2,5\right]$

. We need to choose atmost 2 distinct integers, we choose

$2,2,5$

. Note that the condition is choosing atmost

$K$

distinct integers. So we can choose repeated number as many times as we want. The sum is

$2+2+5=9$

and we output it.

$10$

Code:-

This solution is based on the c++ language and you can submit it c++14 and c++17 also.
In this solution first three lines of the main function is only for the decreasing the time of execution of the program..
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

This is your choice that you want to use this or not but in some cases the code may take more time in execution and that time we need it .

#include<bits/stdc++.h>
#define ll long long int
#define pb push_back
#define nline “n”
#define f first
#define s second
#define um unordered_map
using namespace std;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin>>t;
while(t–){
int n,k;
cin>>n>>k;
um<ll,ll>m;
for (int i = 0; i < n; i++)
{
ll a;
cin>>a;
m[a] += a;
}
vector<ll>v;
for(auto &val:m){
v.pb(val.s);
}
sort(v.begin(), v.end(),greater<ll>());
ll sum = 0;
for (int i = 0; i < k; i++)
{
if(sum+v[i] > sum) sum += v[i];
}
cout<<sum<<nline;
}

return 0;
}

Recommended Post:-

MCQs:-