Teaching Kids Programming – Find Subsequence of Length K With the Largest Sum (Greedy, Sliding Window)

Teaching Kids Programming: Videos on Data Structures and Algorithms

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].

Hints:
From a greedy perspective, what k elements should you pick?
Could you sort the array while maintaining the index?

Find Subsequence of Length K With the Largest Sum (Greedy Sort)

We can sort the numbers to pick K elements from largest to smallest – however we need to remember their indices. We can use enumerate function to give us the tuple for index and value, then we sort the array but the value. Then we pick the indices for the largest K elements and sort the indices and finally construct the subsequence.

1
2
3
4
5
6
7

class Solution:
    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:
        arr = list(enumerate(nums))
        arr.sort(key = lambda x: x[1])
        idx = [i for i, j in arr[-k:]]
        idx.sort()
        return [nums[i] for i in idx]

class Solution:
    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:
        arr = list(enumerate(nums))
        arr.sort(key = lambda x: x[1])
        idx = [i for i, j in arr[-k:]]
        idx.sort()
        return [nums[i] for i in idx]

Time complexity is O(NLogN) as we are sorting the array twice. And the space complexity is O(N) as we have an additional array to keep the tuples (index and value).

Find Subsequence of Length K With the Largest Sum (Sliding Window)

We can keep a sliding window of fixed size K, then iterating through the elements from index K, remove the element from the window and append to the end of the window if the current element is larger than the min of the window.

1
2
3
4
5
6
7
8
9
10
11

class Solution:
    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        assert 0 <= k <= n
        window = nums[:k]
        for i in range(k, n):
            curMin = min(window)
            if nums[i] > curMin:
                window.remove(curMin)
                window.append(nums[i])
        return window

class Solution:
    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        assert 0 <= k <= n
        window = nums[:k]
        for i in range(k, n):
            curMin = min(window)
            if nums[i] > curMin:
                window.remove(curMin)
                window.append(nums[i])
        return window

The time complexity is O(NK) where K is no larger than K, and thus the time complexity is O(N^2) which is slower than the above sorting algorithm.

–EOF (The Ultimate Computing & Technology Blog) —