Grade 11 · The greedy methodCitește în română

Maximum sum with k elements

Original: Suma maximă cu k elemente

O(n log n)C++1751 lines1 example

The idea

From a sequence of n integers we choose exactly k elements (on different positions) with the largest possible sum. The greedy choice is obvious: take the k largest values. We get them by sorting the sequence in decreasing order and keeping the first k. The sum and the chosen elements, from largest to smallest, are printed.

Original description (Romanian)

Dintr-un șir de n numere întregi alegem exact k elemente (pe poziții diferite) cu suma cât mai mare. Alegerea greedy este evidentă: luăm cele mai mari k valori. Le obținem sortând șirul descrescător și păstrând primele k. Se afișează suma și elementele alese, de la cel mai mare la cel mai mic.

Complexity
O(n log n)
Grade
Grade 11 (Clasa a XI-a)

Examples

Example 1

Input

6 3
4 -2 7 -5 3 1

Expected output

14
7 4 3

The code

Comments are in Romanian, as in the original collection. Edit freely: you can reset at any time.

suma-maxima-cu-k-elemente.cpp
/*
 * Titlu: Suma maximă cu k elemente
 * Clasa: 11
 * Capitol: Metoda greedy
 * Descriere: Dintr-un șir de n numere întregi alegem exact k elemente (pe poziții
 *            diferite) cu suma cât mai mare. Alegerea greedy este evidentă: luăm cele mai
 *            mari k valori. Le obținem sortând șirul descrescător și păstrând primele k.
 *            Se afișează suma și elementele alese, de la cel mai mare la cel mai mic.
 * Complexitate: O(n log n)
 *
 * Exemplu
 * Intrare:
 * 6 3
 * 4 -2 7 -5 3 1
 * Ieșire:
 * 14
 * 7 4 3
 */
#include <iostream>
#include <algorithm>
using namespace std;

bool descrescator(int x, int y)
{
    return x > y;
}

int main()
{
    int n, k, a[1000];
    cin >> n >> k;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    sort(a, a + n, descrescator);

    long long suma = 0;
    for (int i = 0; i < k; i++)
    {
        suma += a[i];
    }
    cout << suma << '\n';
    for (int i = 0; i < k; i++)
    {
        cout << a[i] << ' ';
    }
    cout << '\n';
    return 0;
}

Runs on a real g++ (C++17, -O2) through Compiler Explorer. Keep runs short; there's a time limit.