This content originally appeared on DEV Community and was authored by MD ARIFUL HAQUE
2099. Find Subsequence of Length K With the Largest Sum
Difficulty: Easy
Topics: Array, Hash Table, Sorting, Heap (Priority Queue)
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.length
Hint:
- From a greedy perspective, what k elements should you pick?
- Could you sort the array while maintaining the index?
Solution:
We need to find a subsequence of length k from the given array nums that has the largest possible sum. A subsequence is derived by deleting some elements without changing the order of the remaining elements. The solution involves selecting the k largest elements from the array and returning them in their original order.
Approach
-
Problem Analysis: The goal is to maximize the sum of a subsequence of length
k. The optimal approach involves selecting theklargest elements in the array. However, these elements must appear in the subsequence in the same order as they appear in the original array. -
Intuition: The largest sum is achieved by selecting the
klargest elements. Since the order of elements in the subsequence must match their original order, we first identify these elements and then sort them by their original indices. -
Algorithm Selection:
- Pair Creation: Create pairs of each element's index and its value.
- Sort by Value: Sort these pairs in descending order based on their values. This ensures the largest elements are considered first.
-
Select Top k Elements: Take the first
kpairs from the sorted list. - Sort by Index: Sort the selected pairs by their original indices to maintain the order in which they appear in the original array.
- Extract Values: Extract the values from the sorted pairs to form the resulting subsequence.
-
Complexity Analysis:
-
Time Complexity: The dominant operations are the two sorting steps. Sorting the entire array takes O(n log n) time, and sorting the
kelements takes O(k log k) time. Since k ≤ n, the overall complexity is O(n log n). - Space Complexity: Additional space is used to store the pairs, which is O(n).
-
Time Complexity: The dominant operations are the two sorting steps. Sorting the entire array takes O(n log n) time, and sorting the
Let's implement this solution in PHP: 2099. Find Subsequence of Length K With the Largest Sum
<?php
/**
* @param Integer[] $nums
* @param Integer $k
* @return Integer[]
*/
function maxSubsequence($nums, $k) {
...
...
...
/**
* go to ./solution.php
*/
}
// Test cases
print_r(maxSubsequence(array(2, 1, 3, 3), 2)); // Output: Array ( [0] => 3 [1] => 3 )
print_r(maxSubsequence(array(-1, -2, 3, 4), 3)); // Output: Array ( [0] => -1 [1] => 3 [2] => 4 )
print_r(maxSubsequence(array(3, 4, 3, 3), 2)); // Output: Array ( [0] => 4 [1] => 3 ) or [3,4]
?>
Explanation:
- Pair Creation: We start by creating an array of pairs where each pair consists of an element's index and its value. This helps in tracking the original positions of elements after sorting.
- Sort by Value: The pairs are sorted in descending order based on their values. This ensures that the largest elements are at the beginning of the array.
-
Select Top k Elements: We slice the first
kelements from the sorted array of pairs, which represent theklargest elements in the array. - Sort by Index: The selected pairs are then sorted by their original indices to ensure the resulting subsequence maintains the order of elements as they appear in the original array.
- Extract Values: Finally, we extract the values from the sorted pairs to form the subsequence, which is returned as the result.
This approach efficiently selects the largest elements while preserving their original order, ensuring the solution meets the problem requirements.
Contact Links
If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!
If you want more helpful content like this, feel free to follow me:
This content originally appeared on DEV Community and was authored by MD ARIFUL HAQUE
MD ARIFUL HAQUE | Sciencx (2025-06-28T00:57:37+00:00) 2099. Find Subsequence of Length K With the Largest Sum. Retrieved from https://www.scien.cx/2025/06/28/2099-find-subsequence-of-length-k-with-the-largest-sum/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.