Question

How to find the maximum value we can achieve by picking k elements from a vector in C++

Answer 1

// Sort and pick the top k (O(n log n))
// Best when n is not extremely large
// Easiest to implement
// Always correct for this problem

#include <iostream>
#include <algorithm>
#include <vector>

int maxSumKElements(std::vector<int>& arr, int k) {
    std::sort(arr.begin(), arr.end(), std::greater<int>()); // sort descending

    int sum = 0;
    for (int i = 0; i < k; i++)
        sum += arr[i];

    return sum;
}

int main() {
    std::vector<int> arr = {11, 2, 4, 9, 3, 6, 5, 1};
    int k = 3;

    std::cout << "Maximum sum = " << maxSumKElements(arr, k) << std::endl;
}



/*
run:

Maximum sum = 26

*/

 

70+ SQL courses for beginners and professionals

Answer 2

// Use a max‑heap (priority queue
// No need to sort the entire array
// Need only the top k elements

#include <iostream>
#include <queue>
#include <vector>

int maxSumKElements(std::vector<int>& arr, int k) {
    std::priority_queue<int> pq(arr.begin(), arr.end());

    int sum = 0;
    while (k--) {
        sum += pq.top();
        pq.pop();
    }
    
    return sum;
}

int main() {
    std::vector<int> arr = {11, 2, 4, 9, 3, 6, 5, 1};
    int k = 3;

    std::cout << "Maximum sum = " << maxSumKElements(arr, k) << std::endl;
}



/*
run:

Maximum sum = 26

*/

 

70+ SQL courses for beginners and professionals

Answer 3

// Use nth_element

#include <iostream>
#include <algorithm>
#include <vector>

int maxSumKElements(std::vector<int>& arr, int k) {
    nth_element(arr.begin(), arr.begin() + k, arr.end(), std::greater<int>());

    int sum = 0;
    for (int i = 0; i < k; i++)
        sum += arr[i];

    return sum;
}

int main() {
    std::vector<int> arr = {11, 2, 4, 9, 3, 6, 5, 1};
    int k = 3;

    std::cout << "Maximum sum = " << maxSumKElements(arr, k) << std::endl;
}



/*
run:

Maximum sum = 26

*/

 

70+ SQL courses for beginners and professionals