出處 : https://leetcode.com/problems/find-subsequence-of-length-k-with-the-largest-sum/submissions/
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] <= 105
1 <= k <= nums.length
找最大的三個數字,但出現的順序不能變:
/** * @param {number[]} nums * @param {number} k * @return {number[]} */ var maxSubsequence = function(nums, k) { // 先排除 k 等於 nums.length 的情形 if (k === nums.length) return nums // 用前 k 個當啜預設的結果進 loop const res = nums.slice(0, k) for (let i = k; i < nums.length; i++) { let min = Infinity let targetIdx = null // 一直比較前 k 的大小,如果有比之前的數字大,就移除就數字,補新數字。 for (let j = 0; j < k; j++) { if (res[j] < min) { min = res[j] targetIdx = j } } if (nums[i] > min) { res.splice(targetIdx, 1) res.push(nums[i]) } } return res };