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.
Example 1:
Input: nums = [2,1,3,3], k = 2 Output: [3,3] Explanation: The subsequence has the largest sum of 3 + 3 = 6.
Example 2:
Input: nums = [-1,-2,3,4], k = 3 Output: [-1,3,4] Explanation: The subsequence has the largest sum of -1 + 3 + 4 = 6.
Example 3:
Input: nums = [3,4,3,3], k = 2 Output: [3,4] Explanation: The subsequence has the largest sum of 3 + 4 = 7. Another possible subsequence is [4, 3].
Constraints:
1 <= nums.length <= 1000-105 <= nums[i] <= 1051 <= k <= nums.lengthApproach: Sort the array of numbers based on their values while remembering their original indices. Then, select the top k elements with the largest values and use their indices to construct the subsequence from the original array.
This approach involves two main steps: sorting the array elements along with their original indices and selecting the largest k elements from this sorted structure. Once the top k elements are found, maintain their original order by using the stored indices.
This program sorts the array based on their values while keeping track of the original indices using a struct. The qsort function is utilized for sorting. After sorting, the top k elements are selected and arranged in the order they originally appeared in the input array.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log n), due to sorting the elements.
Space Complexity: O(n), required for storing elements and indices.
Approach: Utilize a Min-Heap (or Priority Queue) to keep track of the k largest elements in the array. This method involves iterating through the array and inserting each element into the heap, ensuring that the heap size does not exceed k. If the heap exceeds k elements, the smallest element is removed. This approach keeps only the top k elements.
Finally, extract the elements from the heap and reconstruct the subsequence in the order they appear in the original array using their indices.
This solution utilizes a Min-Heap in Java's PriorityQueue. Each entry in the queue is a pair consisting of the number and its index. As we iterate through the array, we keep adding pairs to the heap and ensure its size remains k by removing the smallest element when necessary. The final list of indices is sorted and used to form the resultant subsequence.
Python
Time Complexity: O(n log k), because each insertion and deletion in the heap takes log k time.
Space Complexity: O(k), for storing the k largest elements.
| Approach | Complexity |
|---|---|
| Sorting and Selecting Top K Elements | Time Complexity: O(n log n), due to sorting the elements. Space Complexity: O(n), required for storing elements and indices. |
| Using Priority Queue (Min-Heap) | Time Complexity: O(n log k), because each insertion and deletion in the heap takes log k time. Space Complexity: O(k), for storing the k largest elements. |
Maximum Subarray - Amazon Coding Interview Question - Leetcode 53 - Python • NeetCode • 605,142 views views
Watch 9 more video solutions →Practice Find Subsequence of Length K With the Largest Sum with our built-in code editor and test cases.
Practice on FleetCode