aboutsummaryrefslogtreecommitdiff
path: root/find_subseq_len_k_large_sum.py
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-06-27 20:26:15 -0600
committerJack Sangdahl <[email protected]>2025-06-27 20:26:15 -0600
commiteb7cdeeb68883d835f8b06e497f7b0d0a63ad05d (patch)
treeb8ccbaae6da807b1d623f62d46e892736e977940 /find_subseq_len_k_large_sum.py
parenta96b65cbfad7f62f3db6b2eab105e4e25c0414c5 (diff)
downloadleetcode-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.py32
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))