欣迪

出處 : 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.

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
};

訂閱 IT-Monk

訂閱最新文章的發布消息! 😚😚😚
Loading

作者介紹 - 欣迪

欣迪

從設計到寫程式,發現自己有追求前端技巧的自虐傾向。不斷的踩坑,再從坑裡爬出來,慢慢對攀岩有點心得。 目前在多間公司擔任網站設計顧問。 同時也是網站架設公司負責人。