IT僧

解題 55. Find Subsequence of Length K With the Largest Sum

24 3 月, 2022 欣迪

出處 : 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
};