Find Subsequence of Length K With the Largest Sum

Find Subsequence of Length K With the Largest Sum

What is this problem about?

The Find Subsequence of Length K With the Largest Sum interview question asks you to pick $k$ elements from an array such that their sum is maximized. The critical requirement is that these elements must maintain their original relative order from the input array (this is what makes it a "subsequence" rather than just a set of numbers).

Why is this asked in interviews?

Companies like Meta and Amazon ask the Find Subsequence of Length K With the Largest Sum coding problem to test a candidate's ability to balance two different requirements: value (choosing the largest numbers) and position (maintaining order). It evaluations your proficiency with Sorting interview patterns and your ability to use indices to reconstruct a sequence.

Algorithmic pattern used

This problem is solved using a Sort-by-Value then Sort-by-Index approach or a Priority Queue.

1. Identify Top K: First, find the $k$ largest elements in the array. Since the array is small, you can sort a list of (value, original_index) pairs in descending order by value.
2. Preserve Order: Take the top $k$ pairs and sort them by their original index in ascending order.
3. Construct Result: Extract the values from these index-sorted pairs. This gives you the largest sum possible while following the subsequence rule.

Example explanation

Array: [2, 1, 3, 3], $k=2$.

1. Pairs: (2,0), (1,1), (3,2), (3,3).
2. Sorted by value (desc): (3,2), (3,3), (2,0), (1,1).
3. Take top $k=2$: (3,2), (3,3).
4. Sorted by index: (3,2), (3,3).
5. Result: [3, 3]. If $k=3$ for [3, 4, 3, 3]:
6. Top 3 values are 4, 3, 3. Their indices are 1, 0, 2 (or 1, 2, 3 etc).
7. Sorting indices ensures they appear in the same order as the input.

Common mistakes candidates make

• Returning Sorted Values: Simply returning the $k$ largest numbers in sorted order, forgetting the subsequence requirement.
• Greedy without Indices: Trying to pick numbers one-by-one without remembering where they came from.
• Complexity: Using a Max-Heap to find $k$ elements is $O(N \log K)$, but you still need to sort those $k$ elements by index at the end.

Interview preparation tip

In problems where you need to pick "best" elements but maintain "order," always store the elements as pairs or objects containing their original index. This is a foundational technique for "Array interview pattern" problems involving subsequences.