# 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$. Your task is to maximize the sum of chosen numbers.

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
2
4 1
3 -1 2 5
4 2
2 1 2 5

Sample Output
5
9

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:-

• Hackerearth Problems:-

Key points:-

MCQs:-