Maximum Sum (Codeforces 1832B)
Tags: Others, two pointers

You are given an array $$$a_1, a_2, \dots, a_n$$$, where all elements are different.You have to perform exactly $$$k$$$ operations with it. During each operation, you do exactly one of the following two actions (you choose which to do yourself):  find two minimum elements in the array, and delete them;  find the maximum element in the array, and delete it. You have to calculate the maximum possible sum of elements in the resulting array.

Input: The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.Each test case consists of two lines:   the first line contains two integers $$$n$$$ and $$$k$$$ ($$$3 \le n \le 2 \cdot 10^5$$$; $$$1 \le k \le 99999$$$; $$$2k < n$$$) — the number of elements and operations, respectively.  the second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$; all $$$a_i$$$ are different) — the elements of the array. Additional constraint on the input: the sum of $$$n$$$ does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case, print one integer — the maximum possible sum of elements in the resulting array.

Note: In the first testcase, applying the first operation produces the following outcome:   two minimums are $$$1$$$ and $$$2$$$; removing them leaves the array as $$$[5, 10, 6]$$$, with sum $$$21$$$;  a maximum is $$$10$$$; removing it leaves the array as $$$[2, 5, 1, 6]$$$, with sum $$$14$$$. $$$21$$$ is the best answer.In the second testcase, it's optimal to first erase two minimums, then a maximum.

Sample Inputs:
6
5 1
2 5 1 10 6
5 2
2 5 1 10 6
3 1
1 2 3
6 1
15 22 12 10 13 11
6 2
15 22 12 10 13 11
5 1
999999996 999999999 999999997 999999998 999999995

Sample Outputs:
21
11
3
62
46
3999999986

Solution (Python):
t = int(input())
for i in range(t):
    (n, k) = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    s = sum(a[:n - k])
    ans = s
    x = 0
    y = n - k
    while y < n:
        s = s + a[y] - (a[x] + a[x + 1])
        x += 2
        y += 1
        ans = max(ans, s)
    print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

def solve():
    (n, k) = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    pre = [0] * (n + 1)
    for i in range(n):
        pre[i + 1] = pre[i] + a[i]
    ans = 0
    for i in range(k + 1):
        y = k - i
        ans = max(ans, pre[n - y] - pre[2 * i])
    print(ans)
t = int(input())
for _ in range(t):
    solve()

Solution (Python):
t = int(input())
for _ in range(t):
    (n, k) = list(map(int, input().split()))
    arr = sorted(map(int, input().split()))
    total_sum = sum(arr[:-k])
    result = total_sum
    i = 0
    j = len(arr) - k
    while i < 2 * k:
        total_sum += arr[j] - arr[i] - arr[i + 1]
        i += 2
        j += 1
        if total_sum > result:
            result = total_sum
    print(result)