Find Subsequence of Length K With the Largest Sum

Difficulty: Easy | Acceptance: 57.40% | Paid: No Topics: Array, Hash Table, Sorting, Heap (Priority Queue)

You are given an integer array nums and an integer k. You want to find a subsequence of nums of length k that has the maximum sum.

Return any subsequence of nums of length k with the maximum sum.

A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

• Examples
• Constraints
• Sorting with Indices
• Heap (Priority Queue)
• Brute Force

Examples

Input: nums = [2,1,3,3], k = 2
Output: [3,3]
Explanation:
The subsequence has the maximum sum of 3 + 3 = 6.

Input: nums = [-1,-2,3,4], k = 3
Output: [-1,3,4]
Explanation:
The subsequence has a maximum sum of -1 + 3 + 4 = 6.

Input: nums = [3,4,3,3], k = 2
Output: [3,4]
Explanation:
The subsequence has the maximum sum of 3 + 4 = 7. 
The other subsequence [3,3] has a sum of 3 + 3 = 6.

Constraints

1 <= nums.length <= 1000
-10⁵ <= nums[i] <= 10⁵
1 <= k <= nums.length

Sorting with Indices

Intuition Pair each element with its index, sort by value to find the k largest elements, then sort those by index to restore original order.

Steps

• Create pairs of (value, index) for all elements
• Sort pairs by value in descending order
• Take the top k pairs
• Sort these k pairs by their original indices
• Extract and return the values

class Solution:
    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:
        indexed = [(nums[i], i) for i in range(len(nums))]
        indexed.sort(key=lambda x: -x[0])
        top_k = indexed[:k]
        top_k.sort(key=lambda x: x[1])
        return [val for val, idx in top_k]

Complexity

• Time: O(n log n)
• Space: O(n)
• Notes: Simple and intuitive, but requires full sorting

Heap (Priority Queue)

Intuition Use a min-heap of size k to track the k largest elements while iterating through the array, then sort by index to maintain order.

Steps

• Create a min-heap of (value, index) pairs
• For each element, push to heap
• If heap size exceeds k, remove the smallest element
• After processing all elements, sort remaining k elements by index
• Return the values in order

import heapq

class Solution:
    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:
        heap = []
        for i, val in enumerate(nums):
            heapq.heappush(heap, (val, i))
            if len(heap) > k:
                heapq.heappop(heap)
        heap.sort(key=lambda x: x[1])
        return [val for val, idx in heap]

Complexity

• Time: O(n log k)
• Space: O(n)
• Notes: More efficient than sorting when k is much smaller than n

Brute Force

Intuition Generate all possible subsequences of length k, calculate their sums, and return the one with maximum sum.

Steps

• Generate all combinations of k indices from the array
• For each combination, calculate the sum of elements at those indices
• Track the combination with maximum sum
• Return the elements of that combination in order

from itertools import combinations

class Solution:
    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        max_sum = float('-inf')
        result = []
        
        for indices in combinations(range(n), k):
            current_sum = sum(nums[i] for i in indices)
            if current_sum > max_sum:
                max_sum = current_sum
                result = [nums[i] for i in indices]
        
        return result

Complexity

• Time: O(n choose k)
• Space: O(k)
• Notes: Exponential time complexity, only suitable for very small inputs