We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find Subsequence of Length K With the Largest Sum

Difficulty: Easy

Problem Description

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.

Key Insights

  • A subsequence can be formed by deleting some or no elements from the array without changing the order of the remaining elements.
  • To maximize the sum of a subsequence of length k, we should select the k largest elements from the array.
  • Sorting the array or using a heap data structure can help efficiently find the largest elements while maintaining their original order.

Space and Time Complexity

Time Complexity: O(n log n) - due to sorting the array.
Space Complexity: O(n) - for storing the original indices of the elements.

Solution

To solve the problem, we can follow these steps:

  1. Pair each element in the nums array with its index.
  2. Sort the pairs based on the values in descending order.
  3. Take the first k elements from the sorted list (these are the largest).
  4. Sort these k elements based on their original indices to maintain the order.
  5. Extract the values from these sorted pairs to form the result subsequence.

This approach ensures that we identify the largest elements while keeping their original ordering in the subsequence.

Code Solutions

def maxSubsequence(nums, k):
    # Pair each number with its index
    indexed_nums = [(num, i) for i, num in enumerate(nums)]
    
    # Sort based on the number in descending order
    indexed_nums.sort(key=lambda x: x[0], reverse=True)
    
    # Get the first k elements
    largest_k = indexed_nums[:k]
    
    # Sort the k elements by their original index
    largest_k.sort(key=lambda x: x[1])
    
    # Extract the numbers from the sorted k elements
    return [num for num, index in largest_k]
← Back to All Questions