Find Subsequence of Length K With the Largest Sum

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

Write a function to solve this problem with optimal time complexity.

def max_subsequence(nums, k):
    """Finds a subsequence of nums of length k that has the largest sum."""

    # 1. Naive approach: Generate all subsequences of length k, calculate their sums,
    # and return the subsequence with the maximum sum.
    # This approach has a time complexity of O(C(n, k)), where n is the length of nums,
    # and C(n, k) is the binomial coefficient "n choose k".

    # 2. Optimal approach:
    #    a. Create a list of (value, index) tuples from the input array.
    #    b. Sort the list in descending order based on the value.
    #    c. Select the top k elements from the sorted list.
    #    d. Sort the selected elements based on their original indices to maintain the original order.
    #    e. Extract the values from the sorted (value, index) tuples.

    indexed_nums = [(nums[i], i) for i in range(len(nums))]
    sorted_nums = sorted(indexed_nums, key=lambda x: x[0], reverse=True)
    top_k = sorted_nums[:k]
    top_k.sort(key=lambda x: x[1])  # Sort by original index
    result = [num for num, index in top_k]

    return result


# Example Usage:
nums1 = [2, 1, 3, 3]
k1 = 2
print(f"Input: nums = {nums1}, k = {k1}\nOutput: {max_subsequence(nums1, k1)}")
# Expected Output: [3, 3]

nums2 = [-1, -2, 3, 4]
k2 = 3
print(f"\nInput: nums = {nums2}, k = {k2}\nOutput: {max_subsequence(nums2, k2)}")
# Expected Output: [-1, 3, 4]

nums3 = [3, 4, 3, 3]
k3 = 2
print(f"\nInput: nums = {nums3}, k = {k3}\nOutput: {max_subsequence(nums3, k3)}")
# Expected Output: [3, 4] or [4, 3]

Code Explanation:

1. max_subsequence(nums, k) Function:
   • Takes the input array nums and the subsequence length k as input.
   • Creates a list indexed_nums containing tuples of (value, index) for each element in nums. This preserves the original index of each number.
   • Sorts indexed_nums in descending order based on the value of the numbers using sorted(indexed_nums, key=lambda x: x[0], reverse=True). This puts the largest numbers at the beginning of the list.
   • Selects the top k elements from the sorted list using top_k = sorted_nums[:k]. These are the k largest numbers.
   • Sorts top_k based on the original indices of the numbers in ascending order using top_k.sort(key=lambda x: x[1]). This ensures that the subsequence maintains the original order of the elements in the input array.
   • Extracts the values from the sorted top_k list into a new list called result.
   • Returns the result list, which represents the subsequence with the largest sum.

Big O Time Complexity Analysis:

• Creating indexed_nums: O(n), where n is the length of the input array nums.
• Sorting indexed_nums: O(n log n), where n is the length of the input array nums.
• Selecting the top k elements: O(k).
• Sorting the top k elements: O(k log k).
• Extracting values into result: O(k).

Therefore, the overall time complexity is O(n log n), dominated by the initial sorting step.

Big O Space Complexity Analysis:

• indexed_nums: O(n) to store the (value, index) tuples.
• sorted_nums: O(n) to store the sorted list of (value, index) tuples.
• top_k: O(k) to store the top k elements.
• result: O(k) to store the final subsequence.

Therefore, the overall space complexity is O(n), dominated by indexed_nums and sorted_nums.

Edge Cases and Handling:

1. Empty Input Array: If the input array nums is empty, the function should return an empty list. The current implementation implicitly handles this case correctly because the loops will not execute if the array is empty.

2. k is Zero: If k is zero, the function should return an empty list. This is also handled correctly because top_k = sorted_nums[:0] will result in an empty list.

3. k is Equal to the Length of nums: If k is equal to the length of nums, the function should return the original array nums or a copy of it (depending on whether in-place modification is allowed). In this case, all elements are selected and sorted based on their index which is equivalent to returning the whole array.

4. Duplicate Numbers: The algorithm correctly handles duplicate numbers by considering their original indices when sorting the top k elements. This ensures that the subsequence maintains the order of elements as present in the original array in case of ties.

5. Negative Numbers: The algorithm handles negative numbers correctly. Sorting in descending order ensures that the largest numbers (including negative numbers closest to zero) are selected.

6. All Numbers are Same: The algorithm works correctly even if all the elements are the same. Sorting will keep the original order.