← Back to Index

📚 Find Subsequence of Length K With the Largest Sum – Java Cheat Sheet

📌 What Is It?

The Find Subsequence of Length K With the Largest Sum problem involves selecting K elements from an array such that their sum is maximized while maintaining their relative order.

This problem can be solved using a max-heap to track the largest elements and then sorting them by their original indices.

🧱 Pattern Template

class Solution {
    public int[] maxSubsequence(int[] nums, int k) {
        PriorityQueue<int[]> maxHeap = new PriorityQueue<>(
            (a, b) -> a[0] - b[0] // Min-heap based on values
        );

        // Step 1: Add elements to the heap and maintain size K
        for (int i = 0; i < nums.length; i++) {
            maxHeap.offer(new int[]{nums[i], i});
            if (maxHeap.size() > k) {
                maxHeap.poll(); // Remove the smallest element
            }
        }

        // Step 2: Extract the top K elements
        List<int[]> topK = new ArrayList<>(maxHeap);

        // Step 3: Sort the elements by their original indices
        topK.sort((a, b) -> a[1] - b[1]);

        // Step 4: Extract the values
        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
            result[i] = topK.get(i)[0];
        }

        return result;
    }
}

📊 Time Complexity

• Heap Operations: O(N log K) – Adding elements to the heap.
• Sorting: O(K log K) – Sorting the top K elements by their indices.
• Overall Complexity: O(N log K).

✅ Use Cases

• Finding subsequences with maximum sums while preserving order
• Applications in optimization problems
• Efficiently processing large datasets

📘 Common LeetCode Problems

• 2099. Find Subsequence of Length K With the Largest Sum [Medium] Heap

🧪 Example: Find Subsequence of Length K With the Largest Sum

Input: nums = [2,1,3,3], k = 2
Output: [3,3]

Explanation:
- The top 2 elements are [3, 3].
- Sorting by their original indices gives [3, 3].

▶️ View Animation

💡 Pro Tips

• Use a max-heap to efficiently track the largest elements.
• Edge cases: arrays with fewer than K elements.
• Ensure the subsequence preserves the original order of elements.