2099. Find Subsequence of Length K With the Largest Sum #1862
-
Topics: You are given an integer array Return any such subsequence as an integer array of length 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:
Example 2:
Example 3:
Constraints:
Hint:
|
Beta Was this translation helpful? Give feedback.
Replies: 1 comment 2 replies
-
We need to find a subsequence of length Approach
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) {
$pairs = [];
$n = count($nums);
for ($i = 0; $i < $n; $i++) {
$pairs[] = [$i, $nums[$i]];
}
usort($pairs, function($a, $b) {
return $b[1] - $a[1];
});
$selected = array_slice($pairs, 0, $k);
usort($selected, function($a, $b) {
return $a[0] - $b[0];
});
$result = [];
foreach ($selected as $pair) {
$result[] = $pair[1];
}
return $result;
}
// 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:
This approach efficiently selects the largest elements while preserving their original order, ensuring the solution meets the problem requirements. |
Beta Was this translation helpful? Give feedback.
We need to find a subsequence of length
k
from the given arraynums
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 thek
largest elements from the array and returning them in their original order.Approach
k
. The optimal approach involves selecting thek
largest elements in the array. However, these elements must appear in the subsequence in the same order as they appear in the original array.k
largest elements. Since the order of el…