Maximum and Minimum Sums of at Most Size K Subsequences - Solution & Explanation

Problem Overview: You receive an integer array and an integer k. Consider every subsequence whose size is at most k. For each subsequence, identify its minimum and maximum element, then accumulate their contributions across all valid subsequences. The goal is to compute the total efficiently without explicitly generating every subsequence.

Approach 1: Brute Force Enumeration (O(2^n * n) time, O(n) space)

The most direct idea is to generate every subsequence using bitmasks or backtracking. For each subsequence, check if its size is ≤ k, then scan the elements to compute the minimum and maximum. Add both values to the running total. This approach is easy to implement but explodes combinatorially because an array of size n has 2^n subsequences. Even moderate input sizes make this impractical, but it helps clarify how minimum and maximum values contribute to the final sum.

Approach 2: Sorting + Combinatorics Contribution Counting (O(n log n + nk) time, O(n) space)

The key observation: instead of enumerating subsequences, count how many subsequences treat a specific element as their minimum or maximum. Start by sorting the array using techniques from sorting. When the array is sorted, elements to the left are smaller and elements to the right are larger. This ordering makes it easy to determine how many subsequences can choose the current element as their minimum or maximum.

For an element at index i, treat it as the maximum. You can choose up to k-1 additional elements from the i elements before it. The number of such subsequences equals the sum of combinations C(i, t) for t = 0..k-1. Similarly, treat the element as the minimum and select up to k-1 elements from the right side. Precompute combinations using techniques from combinatorics or dynamic programming so each query is constant time. Multiply the element value by the number of subsequences where it acts as min or max, and accumulate the contribution.

This transforms an exponential enumeration problem into a counting problem. Instead of building subsequences, you iterate through the array once and use combinatorial counts to measure how often each value participates.

Approach 3: Dynamic Programming for Combination Prefix Sums (O(nk) time, O(nk) space)

If combination values are needed frequently, precompute C(n, r) using a Pascal triangle style dynamic programming table. Build combination values up to n and k, then maintain prefix sums of combinations so the number of ways to choose ≤ k-1 elements can be retrieved quickly. This reduces repeated summation when calculating contributions for each index. The overall logic stays the same: count subsequences where each element becomes the minimum or maximum.

Recommended for interviews: The sorting + combinatorics contribution approach is what interviewers expect. Brute force shows understanding of the subsequence definition, but recognizing that each element's contribution can be counted with combinations demonstrates stronger algorithmic insight and familiarity with counting techniques.