Maximum and Minimum Sums of at Most Size K Subsequences

Maximum and Minimum Sums of at Most Size K Subsequences

What is this problem about?

(Note: Problem specifics dictate combinatorial bounds). In this problem, you are given an array of integers and an integer k. You must consider all possible subsequences of the array that have a length of at most k. For every single valid subsequence, you find its maximum element and its minimum element, and sum them. Your goal is to return the grand total of these sums across all valid subsequences, modulo $10^9 + 7$.

Why is this asked in interviews?

This is a Hard-level Combinatorics problem. Interviewers use it to separate mathematically mature engineers from those who just memorize algorithms. It tests whether a candidate can shift their perspective from "evaluating sequences" to "evaluating individual elements." It requires using Sorting and N-Choose-K combinatorial math to find out exactly how many sequences a specific number acts as the maximum or minimum.

Algorithmic pattern used

This problem leverages Sorting and Combinatorial Math.

1. Sort the array. Sorting doesn't change subsequences' max/min elements.
2. If the array is sorted, an element at index i will be the maximum element for any subsequence formed entirely of elements to its left (indices $0$ to $i-1$).
3. To form a subsequence of size $\le k$ where arr[i] is the max, we must choose $j$ elements (where $0 \le j \le k-1$) from the $i$ elements to its left. The number of such sequences is $\sum_{j=0}^{k-1} \binom{i}{j}$.
4. We multiply arr[i] by this combinatorial count and add it to the total.
5. We apply symmetrical logic to find how many times arr[i] acts as the minimum (choosing elements from its right).

Example explanation

Array [1, 2, 3], k = 2. Sorted: [1, 2, 3]. Let's find how many sequences of size $\le 2$ where 3 (idx 2) is the Max. Elements to its left: 1, 2 (count is 2). We need to form sequences of size 1 and 2 including the 3.

• Choose 0 elements from left (sequence size 1): $\binom{2}{0} = 1$. (Sequence [3]).
• Choose 1 element from left (sequence size 2): $\binom{2}{1} = 2$. (Sequences [1, 3], [2, 3]). The number 3 is the max in 3 sequences. We add $3 \times 3 = 9$ to our total sum. We repeat this for every element acting as a Max, and every element acting as a Min, calculating permutations on the fly.

Common mistakes candidates make

The fatal flaw is trying to generate the subsequences. Even if $K$ is small, the number of subsequences grows factorially, leading to an immediate Time Limit Exceeded. Another common error is failing to precompute factorials and their modular inverses. Since calculating combinations $\binom{n}{r}$ repeatedly is slow, precomputing arrays of factorials guarantees $O(1)$ lookup time for the combinatorial math.

Interview preparation tip

When an interview question asks for the sum of max/min elements across all possible combinations/subsequences, the template is always the same: Sort the array. Iterate through the elements. Treat the current element as the "King" (max) or "Peasant" (min). Use $\binom{N}{K}$ to count its subjects, multiply its value by that count, and sum it up. This mathematical pivot is a guaranteed "Strong Hire" signal.