[Leetcode] 2099. Find Subsequence of Length K With the Largest Sum

https://leetcode.com/problems/find-subsequence-of-length-k-with-the-largest-sum/description/

initial

So its a subsequence that MUST PRESERVER THE ORIGINAL ORDER. But i just sorted the nums array and greedily took the k highest values. So when i tried to rebuild the answer array of k length, the original order wasnt preserved so I had error.

Actually how do we preserve the original order, while sorting the array? Before any sorting, we can pair each number with its index with enumerate that acts like a positional memory to each number. Then we can sort based on the value, slice till k and sort on the index.

revisited 8/8 2025

yea i thought of heap way but i didnt think of building the answer list cuz the order of subsequence isnt preserved in heap. We can counter(heap) and iter through original list and if theres freq>0 for that number, we add to answer list.

sol

from collections import deque
class Solution:
    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:
        if k==len(nums):
            return nums
        tmp=[]
        for index,num in enumerate(nums):
            tmp.append((num,index))
        tmp.sort(key=lambda x:-x[0])
        nums = tmp[:k]
        nums.sort(key=lambda x:x[1])
        ans=[]
        for num,index in nums:
            ans.append(num)
        return ans
        

heap way

u can also do a similar way using heap to take k largest values first.

    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:
        heap = []
        for n in nums:
            heapq.heappush(heap, n)
            if len(heap) > k:
                heapq.heappop(heap)
        cnt = Counter(heap)
        res = []
        for n in nums:
            if cnt[n] > 0:
                cnt[n] -= 1
                res.append(n)
        return res

complexity

n log n time for my sorting sol
n * log n for heap sol also cuz each heap operation is log n? its not log n but log k cuz
These operations on a heap of size k take O(log k) time.

n space