Introduction

The Slow Sums problem is a greedy algorithm puzzle: given an array of positive integers, you repeatedly pick two numbers, replace them with their sum, and accumulate a penalty equal to that sum. The goal is to maximize the total penalty. The key insight is that numbers added earlier contribute to more penalties — so you should always sum the two largest numbers first.

Problem Statement

Given an array of positive integers, repeatedly perform the following until one number remains:

1. Pick any two numbers from the array
2. Replace them with their sum
3. Add the sum to a running penalty total

Maximize the total penalty.

Example

Array: [4, 2, 1, 3]

Greedy (optimal) — sum largest first:

Sort descending: [4, 3, 2, 1]

1. Sum 4 + 3 = 7, penalty = 7, array = [7, 2, 1]
2. Sum 7 + 2 = 9, penalty = 7 + 9 = 16, array = [9, 1]
3. Sum 9 + 1 = 10, penalty = 16 + 10 = 26, array = [10]

Total penalty: 26

Non-optimal — sum smallest first:

1. Sum 1 + 2 = 3, penalty = 3, array = [4, 3, 3]
2. Sum 3 + 3 = 6, penalty = 3 + 6 = 9, array = [4, 6]
3. Sum 4 + 6 = 10, penalty = 9 + 10 = 19, array = [10]

Total penalty: 19 (less than 26)

Why Greedy Works

When you sum two numbers, the result carries forward into future sums. A number that is summed in step 1 participates in steps 2, 3, and so on — its value is effectively counted multiple times. By summing the largest numbers first, they accumulate the most repeated contributions to the penalty.

Formally: if you sort the array in descending order as a[0] >= a[1] >= ... >= a[n-1], the maximum penalty is:

penalty = a[0] * (n-1) + a[1] * (n-1) + a[2] * (n-2) + ... + a[n-1] * 1

Wait — that is the formula for a different formulation. The actual implementation is simpler: just always combine the two largest elements.

Implementation

Python

1import heapq
2
3def slow_sums(arr):
4    # Use a max-heap (negate values since heapq is a min-heap)
5    max_heap = [-x for x in arr]
6    heapq.heapify(max_heap)
7
8    total_penalty = 0
9
10    while len(max_heap) > 1:
11        # Pop two largest
12        first = -heapq.heappop(max_heap)
13        second = -heapq.heappop(max_heap)
14
15        combined = first + second
16        total_penalty += combined
17
18        # Push the sum back
19        heapq.heappush(max_heap, -combined)
20
21    return total_penalty
22
23print(slow_sums([4, 2, 1, 3]))  # 26

Alternative: Sort-Based (Simpler)

Since after each combination the result is always >= any remaining element (we combined the two largest), we can use a simple sorted approach:

1def slow_sums_sort(arr):
2    arr.sort(reverse=True)
3    total_penalty = 0
4    running_sum = arr[0]
5
6    for i in range(1, len(arr)):
7        running_sum += arr[i]
8        total_penalty += running_sum
9
10    return total_penalty
11
12print(slow_sums_sort([4, 2, 1, 3]))  # 26

This works because after sorting, we always add the next-largest number to the running sum. Each addition produces a penalty equal to the running sum.

C++

1#include <vector>
2#include <queue>
3#include <iostream>
4
5long long slowSums(std::vector<int>& arr) {
6    std::priority_queue<int> maxHeap(arr.begin(), arr.end());
7    long long totalPenalty = 0;
8
9    while (maxHeap.size() > 1) {
10        int first = maxHeap.top(); maxHeap.pop();
11        int second = maxHeap.top(); maxHeap.pop();
12
13        int combined = first + second;
14        totalPenalty += combined;
15        maxHeap.push(combined);
16    }
17
18    return totalPenalty;
19}

JavaScript

1function slowSums(arr) {
2    arr.sort((a, b) => b - a);
3    let totalPenalty = 0;
4    let runningSum = arr[0];
5
6    for (let i = 1; i < arr.length; i++) {
7        runningSum += arr[i];
8        totalPenalty += runningSum;
9    }
10
11    return totalPenalty;
12}
13
14console.log(slowSums([4, 2, 1, 3]));  // 26

Time Complexity

Both approaches are O(n log n) overall. The sort-based approach is simpler and has better constants.

Proof of Correctness

Claim: Always combining the two largest numbers maximizes the total penalty.

Intuition: Each number's contribution to the total penalty equals its value multiplied by the number of times it participates in a combination. Numbers combined earlier participate in more subsequent combinations. By prioritizing larger numbers, their multiplicative effect is maximized.

Exchange argument: Suppose an optimal solution combines two non-largest numbers a and b (where a larger number c exists). Swapping to combine c instead of the smaller number always increases or maintains the penalty, because c > a (or c > b) and the larger value contributes to more future sums.

Variations

Minimize Penalty (Fast Sums)

The opposite problem — minimize the total penalty by summing the smallest first:

1def fast_sums(arr):
2    heapq.heapify(arr)  # min-heap
3    total_penalty = 0
4
5    while len(arr) > 1:
6        first = heapq.heappop(arr)
7        second = heapq.heappop(arr)
8        combined = first + second
9        total_penalty += combined
10        heapq.heappush(arr, combined)
11
12    return total_penalty
13
14print(fast_sums([4, 2, 1, 3]))  # 19 (minimum penalty)

This is equivalent to the optimal merge pattern (Huffman coding without the tree).

Common Pitfalls

• Integer overflow: For large arrays with large values, the penalty can exceed 32-bit integer range. Use long long (C++), BigInt (JavaScript), or Python's arbitrary-precision integers.
• Using a min-heap instead of max-heap: The problem asks to maximize penalty, so you need a max-heap. In Python, negate values to simulate a max-heap with heapq.
• Not recognizing the sort optimization: The sort-based approach is simpler and faster than the heap approach for this specific problem. After sorting, the running sum is always the largest element, so no re-heaping is needed.
• Confusing with Huffman coding: The minimum penalty version (sum smallest first) is equivalent to Huffman coding. The maximum penalty version (this problem) is the opposite — sum largest first.
• Empty or single-element arrays: Handle edge cases: an empty array has 0 penalty, and a single-element array also has 0 penalty (no combinations possible).

Summary

• Always combine the two largest numbers to maximize the total penalty
• Sort the array descending and accumulate a running sum — O(n log n) time, O(1) extra space
• Alternatively, use a max-heap for a more general approach
• The opposite problem (minimize penalty) sums the two smallest — equivalent to Huffman coding
• Total penalty can be very large — use 64-bit integers or arbitrary-precision arithmetic