Untitled

import java.util.*;

public class LargestSumSubsequence {
    public int[] maxSubsequence(int[] nums, int k) {
        // Step 1: Pair each element with its index
        PriorityQueue<int[]> minHeap = new PriorityQueue<>(k, (a, b) -> a[0] - b[0]); // Min-Heap

        for (int i = 0; i < nums.length; i++) {
            minHeap.offer(new int[]{nums[i], i}); // Add value and index to the heap

            // If heap size exceeds k, remove the smallest element
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }

        // Step 2: Collect the top k elements and their indices
        List<int[]> topK = new ArrayList<>(minHeap);
        topK.sort((a, b) -> a[1] - b[1]); // Sort by original indices

        // Step 3: Extract the result while maintaining order
        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
            result[i] = topK.get(i)[0];
        }

        return result;
    }

    public static void main(String[] args) {
        LargestSumSubsequence solution = new LargestSumSubsequence();

        int[] nums1 = {2, 1, 3, 3};
        int k1 = 2;
        System.out.println(Arrays.toString(solution.maxSubsequence(nums1, k1))); // Output: [3, 3]

        int[] nums2 = {-1, -2, 3, 4};
        int k2 = 3;
        System.out.println(Arrays.toString(solution.maxSubsequence(nums2, k2))); // Output: [-1, 3, 4]

        int[] nums3 = {3, 4, 3, 3};
        int k3 = 2;
        System.out.println(Arrays.toString(solution.maxSubsequence(nums3, k3))); // Output: [3, 4]
    }
}