Find Subsequence of Length K With the Largest Sum Interview Question for Amazon

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
-10^5 <= nums[i] <= 10^5
1 <= k <= nums.length

Can you write a function that efficiently finds a subsequence of length k with the largest sum?

Naive Solution

A brute force solution would involve generating all possible subsequences of length k from the input array nums, calculating the sum of each subsequence, and then selecting the subsequence with the largest sum. This approach has a time complexity that makes it impractical for larger input sizes.

Algorithm

Generate all possible subsequences of length k from nums.
Calculate the sum of each subsequence.
Find the subsequence with the maximum sum.
Return the subsequence.

Big O Analysis

Time Complexity: O(C(n, k)), where C(n, k) is the binomial coefficient "n choose k", representing the number of ways to choose k elements from a set of n elements. This is because we need to generate all possible subsequences.
Space Complexity: O(k), to store the current subsequence being considered.

Optimal Solution

A more efficient approach involves these steps:

Sort the elements along with their original indices.
Select the k largest elements.
Sort the k largest elements based on their original indices to maintain the original order.

Algorithm

Create an array of pairs (value, index) from the input array nums.
Sort the array of pairs based on the value in descending order.
Select the first k pairs from the sorted array.
Sort the selected k pairs based on their original indices.
Extract the values from the sorted pairs to form the subsequence.
Return the subsequence.

Edge Cases

If k is equal to the length of nums, return the original nums array.
If nums contains duplicate values, the algorithm should correctly select k elements regardless of their position.

Code

def largest_subsequence(nums, k):
    # Create a list of (value, index) pairs
    indexed_nums = [(val, i) for i, val in enumerate(nums)]

    # Sort by value in descending order
    indexed_nums.sort(key=lambda x: x[0], reverse=True)

    # Select the top k elements
    top_k = indexed_nums[:k]

    # Sort by index to maintain original order
    top_k.sort(key=lambda x: x[1])

    # Extract the values
    result = [val for val, _ in top_k]

    return result

Big O Analysis

Time Complexity: O(n log n) due to sorting the array of (value, index) pairs. Selecting the top k and sorting them again takes O(n + k log k), but O(n log n) dominates.
Space Complexity: O(n) to store the array of pairs.