aboutsummaryrefslogtreecommitdiff
path: root/find_subseq_len_k_large_sum.py
diff options
context:
space:
mode:
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))