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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find Subsequence of Length K With the Largest Sum

Number: 2204

Difficulty: Easy

Paid? No

Companies: Oracle, Accenture

Problem Description

Given an integer array nums and an integer k, find any subsequence of nums of length k that has the largest sum. The subsequence must keep the same relative order as in the original array.

Key Insights

  • The problem asks for a subsequence, not a contiguous segment.
  • We need to choose k elements from the array that maximize the sum.
  • The relative order of the selected elements must be preserved.
  • One effective approach is to select the top k elements by value, then sort these selected elements by their original indices to maintain order.
  • Alternatively, a min-heap of size k can be maintained while traversing the array to achieve O(n log k) time.

Space and Time Complexity

Time Complexity: O(n log n) using sorting or O(n log k) using a min-heap
Space Complexity: O(n) to store index-value pairs or O(k) for the heap

Solution

The algorithm involves two main steps:

  1. Iterate over nums and record each element along with its original index.
  2. Select the k largest elements by value; if values are equal, the relative order (i.e., original index) will help in preserving the subsequence integrity.
  3. After selecting the k largest elements, sort them by their original indices to restore the order as it appears in nums.
  4. Return the values in this sorted order as the subsequence with the largest sum.

This approach leverages sorting (or a heap) to pick the largest values and then uses sorting again to maintain the original subsequence order.

Code Solutions

Below are the sample solutions in Python, JavaScript, C++, and Java.

# Python solution using sorting of (value, index) pairs

def maxSubsequence(nums, k):
    # Create a list of tuples, each containing the value and its original index.
    indexed_nums = [(num, idx) for idx, num in enumerate(nums)]
    
    # Sort the list by value in descending order.
    # If two elements have the same value, their order in the input guarantees that the correct one is chosen
    indexed_nums.sort(key=lambda x: x[0], reverse=True)
    
    # Choose the top k elements for largest sum.
    selected = indexed_nums[:k]
    
    # Sort the selected elements by their original index to maintain subsequence order.
    selected.sort(key=lambda x: x[1])
    
    # Extract and return the values from the sorted selected tuples.
    return [num for num, _ in selected]

# Example usage
print(maxSubsequence([2,1,3,3], 2))  # Output: [3, 3]
← Back to All Questions