diff options
author | Jack Sangdahl <[email protected]> | 2025-06-27 20:26:15 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-06-27 20:26:15 -0600 |
commit | eb7cdeeb68883d835f8b06e497f7b0d0a63ad05d (patch) | |
tree | b8ccbaae6da807b1d623f62d46e892736e977940 /find_subseq_len_k_large_sum.py | |
parent | a96b65cbfad7f62f3db6b2eab105e4e25c0414c5 (diff) | |
download | leetcode-eb7cdeeb68883d835f8b06e497f7b0d0a63ad05d.tar.gz leetcode-eb7cdeeb68883d835f8b06e497f7b0d0a63ad05d.zip |
2099. find subsequence of length k with the largest sum
Diffstat (limited to 'find_subseq_len_k_large_sum.py')
-rw-r--r-- | find_subseq_len_k_large_sum.py | 32 |
1 files changed, 32 insertions, 0 deletions
diff --git a/find_subseq_len_k_large_sum.py b/find_subseq_len_k_large_sum.py new file mode 100644 index 0000000..c7ce933 --- /dev/null +++ b/find_subseq_len_k_large_sum.py @@ -0,0 +1,32 @@ +# 2099. Find Subsequence of Length K With the Largest Sum +import heapq + +""" +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 largest sum. return any such +subsequence as an integer array of length 'k'. 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. +""" + + +class Solution(object): + def maxSubsequence(self, nums, k): + """ + :type nums: List[int] + :type k: int + :rtype: List[int] + """ + heap = [] + for i, j in enumerate(nums): + heapq.heappush(heap, (j, i)) + if len(heap) > k: + heapq.heappop(heap) + return [i[0] for i in sorted(heap, key=lambda x: x[1])] + + +if __name__ == "__main__": + obj = Solution() + print(obj.maxSubsequence(nums=[2, 1, 3, 3], k=2)) + print(obj.maxSubsequence(nums=[-1, -2, 3, 4], k=3)) + print(obj.maxSubsequence(nums=[3, 4, 3, 3], k=2)) |