Problem of The Day: Find Subsequence of Length K With the Largest Sum

Problem Statement

leetcode problem link

Brute Force [Accepted]

class Solution:
    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:
        arr = [(v, i) for i, v in enumerate(nums)]
        sorted_nums = sorted(arr, reverse=True)
        temp = sorted_nums[:k]
        temp.sort(key=lambda x: x[1])
        return [v for v, _ in temp]

Editorial

Approach: Sorting

class Solution:
    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        vals = [[i, nums[i]] for i in range(n)]  # auxiliary array
        # sort by numerical value in descending order
        vals.sort(key=lambda x: -x[1])
        # select the first k elements and sort them in ascending order by index
        vals = sorted(vals[:k])
        res = [val for idx, val in vals]  # target subsequence
        return res