Find Subsequence of Length K With the Largest Sum

Find Subsequence of Length K With the Largest Sum - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: nums = [2,1,3,1], k = 2

› Output: [2,3]

💡 Note: The subsequence has the largest sum among all subsequences of length 2. We select the largest values 3 and 2 while maintaining their original order.

Example 2 — All Positive Numbers

$ Input: nums = [-1,-2,3,4], k = 3

› Output: [-1,3,4]

💡 Note: The 3 largest values are 4, 3, and -1. In original order: [-1,3,4]. Sum = -1 + 3 + 4 = 6.

Example 3 — Single Element

$ Input: nums = [3,4,3,3], k = 2

› Output: [4,3]

💡 Note: We need any 2 elements with largest sum. The largest value 4 and any 3 will do. Taking indices [1,2] gives us [4,3].

Constraints

1 ≤ nums.length ≤ 1000
1 ≤ k ≤ nums.length
-10⁵ ≤ nums[i] ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input

Array nums=[2,1,3,1] and k=2

Process

Find 2 largest values: 3 and 2

Output

Return [2,3] maintaining original order

Key Takeaway

🎯 Key Insight: We must find k largest values but preserve their relative positions from the original array

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to identify the k largest elements while preserving their relative order from the original array. The optimal Sort-First approach pairs each value with its index, sorts by value, selects the k largest, then restores original order. Time: O(n log n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Generate All Subsequences	O(2^n)	O(k)	Generate all possible subsequences of length k and find the one with maximum sum
Min-Heap Approach	O(n log k)	O(k)	Use a min-heap to efficiently track the k largest elements while preserving their original indices
Sort and Select Approach	O(n log n)	O(n)	Sort elements by value while tracking original indices, then select k largest in original order

Brute Force - Generate All Subsequences — Algorithm Steps

Step 1: Generate all possible combinations of k indices from the array
Step 2: For each combination, calculate the sum of elements
Step 3: Track the combination with maximum sum and return those elements

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate

Create all possible combinations of k indices

Calculate

Sum elements for each combination

Select

Choose combination with maximum sum

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int* solution(int* nums, int numsSize, int k, int* returnSize) {
    *returnSize = k;
    long long maxSum = LLONG_MIN;
    int* bestIndices = (int*)malloc(k * sizeof(int));
    
    // Generate all combinations using bit manipulation
    for (int mask = 0; mask < (1 << numsSize); mask++) {
        int bitCount = __builtin_popcount(mask);
        if (bitCount == k) {
            long long currentSum = 0;
            int indices[20]; // Assuming max 20 elements
            int idx = 0;
            
            for (int i = 0; i < numsSize; i++) {
                if (mask & (1 << i)) {
                    indices[idx++] = i;
                    currentSum += nums[i];
                }
            }
            
            if (currentSum > maxSum) {
                maxSum = currentSum;
                for (int i = 0; i < k; i++) {
                    bestIndices[i] = indices[i];
                }
            }
        }
    }
    
    int* result = (int*)malloc(k * sizeof(int));
    for (int i = 0; i < k; i++) {
        result[i] = nums[bestIndices[i]];
    }
    
    free(bestIndices);
    return result;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array manually
    int nums[100];
    int numsSize = 0;
    char* token = strtok(line + 1, ",]"); // Skip opening bracket
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int k;
    scanf("%d", &k);
    
    int returnSize;
    int* result = solution(nums, numsSize, k, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^n)

We generate all possible combinations which is exponential in nature

⚠ Quadratic Growth

Space Complexity

O(k)

Only need space to store the result subsequence of length k

✓ Linear Space

23.5K Views

Medium Frequency

~15 min Avg. Time

850 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Generate All Subsequences — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler