Maximum Weight Difference

Chef and his son bought N items.
Item i weighs Wi grams.

The son insists on carrying some items, under these rules:

The items are split into two groups.
One group contains exactly K items.
Chef carries the heavier group.
His son carries the other group.

Chef wants the difference between his weight and his son’s weight to be as large as possible (while the son is still happy with the rule).

Your task: For each test case, compute the maximum possible difference:

Difference = (Chef's total weight) - (Son's total weight)

Key Idea:

Let:

Total sum of weights: S = ∑ (i=1 to N) Wi

We must choose exactly K items to form the son’s set or choose N-K items for the son, because the rule only fixes group size but does not say which group belongs to whom; Chef always takes the heavier one.

Two scenarios:

Son gets K items:

Let sumK = sum of those K items.
Then Chef’s weight = S - sumK.

Difference (Chef - Son) =
(S-sumK)-sumK=S-2⋅sumK

To maximize this, we want sumK as small as possible.
So son should get the K lightest items.

Son gets N-K items:

Let sumNminusK = sum of those N-K items.
Then Chef’s weight = S - sumNminusK.

Difference =
(S-sumNminusK)-sumNminusK=S-2⋅sumNminusK

Again, to maximize this, we want sumNminusK as small as possible.
So son should get the (N-K) lightest items.

So we just need:

Sort weights.
Compute sumK = sum of K smallest items.
Compute sumNminusK = sum of (N-K) smallest items.
Compute two differences:

diff1 = S - 2 * sumK
diff2 = S - 2 * sumNminusK

Answer = max(diff1, diff2).

Reason: we don’t decide in advance whether kid’s group is size K or N-K; we choose whichever gives maximum difference, because Chef takes the heavier group.

Example Walkthrough:

Sample 1:

N = 5, K = 2
Weights: [8, 4, 5, 2, 10]