[Java/Python 3] From O(n * logn) to average O(n) w/ brief explanation and analysis.
Method 1: Sort\n\nSort the whole array\n1. Combine each index with its corresponding value to create a 2-d array;\n2. Sort the 2-d array reversely by value, the
**Method 1: Sort**\n\n*Sort the whole array*\n1. Combine each index with its corresponding value to create a 2-d array;\n2. Sort the 2-d array reversely by value, then copy the largest k ones;\n3. Sort the largest k ones by index, then return the corresponding values by index order.\n\n```java\n    public int[] maxSubsequence(int[] nums, int k) {\n        int n = nums.length;\n        int[][] indexAndVal = new int[n][2];\n        for (int i = 0; i < n; ++i) {\n            indexAndVal[i] = new int[]{i, nums[i]};\n        }\n        // Reversely sort by value.\n        Arrays.sort(indexAndVal, Comparator.comparingInt(a -> -a[1]));\n        int[][] maxK = Arrays.copyOf(indexAndVal, k);\n        // Sort by index.\n        Arrays.sort(maxK, Comparator.comparingInt(a -> a[0]));\n        int[] seq = new int[k];\n        for (int i = 0; i < k; ++i) {\n            seq[i] = maxK[i][1];\n        }\n        return seq;\n    }\n```\n```python\n    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n        val_and_index = sorted([(num, i) for i, num in enumerate(nums)])\n        return [num for num, i in sorted(val_and_index[-k :], key=lambda x: x[1])]\n```\n\n**Analysis:**\n\nTime: `O(n * logn)`, space: `O(n)`.\n\n----\n\n**Method 2: PriorityQueue/heap**\n\n**Two Passes**\n\n1. Travse input and use PriorityQueue / heap to store `k` largest items, poll out if its size bigger than `k`;\n2. Use Map/dict to store the `k` items in 1.;\n3. Traverse input again, if encounter any item in the afore-mentioned Map/ dict, save it into the output array, then remove the item from the Map/dict.\n```java\n    public int[] maxSubsequence(int[] nums, int k) {\n        PriorityQueue<Integer> pq = new PriorityQueue<>(k + 1);\n        for (int n : nums) {\n            pq.offer(n);\n            if (pq.size() > k) {\n                pq.poll();\n            }\n        }\n        Map<Integer, Integer> freq = new HashMap<>();\n        for (int n : pq) {\n            freq.merge(n, 1, Integer::sum);\n        }\n        int[] seq = new int[k]; \n        int i = 0;\n        for (int n : nums) {\n            if (freq.merge(n, -1, Integer::sum) >= 0) {\n                seq[i++] = n;\n            }\n        }\n        return seq;\n    }\n```\n```python\n    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n        heap = []\n        for n in nums:\n            heapq.heappush(heap, n)\n            if len(heap) > k:\n                heapq.heappop(heap)\n        cnt = Counter(heap)\n        res = []\n        for n in nums:\n            if cnt[n] > 0:\n                cnt[n] -= 1\n                res.append(n)\n        return res\n```\n\n----\n\n*Simplified the above to **One pass*** - credit to **@climberig**\n\nStore indexes of the input array by PriorityQueue/heap, and get rid of Map/dict.\n\n```java\n    public int[] maxSubsequence(int[] nums, int k) {\n        PriorityQueue<Integer> pq = new PriorityQueue<>\n                    (Comparator.comparingInt(i -> nums[i]));\n        for (int i = 0; i < nums.length; ++i) {\n            pq.offer(i);\n            if (pq.size() > k) {\n                pq.poll();\n            }\n        }\n        return pq.stream().sorted().mapToInt(i -> nums[i]).toArray();\n    }\n```\n```python\n    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n        heap = []\n        for i, n in enumerate(nums):\n            heapq.heappush(heap, (n, i))\n            if len(heap) > k:\n                heapq.heappop(heap)\n        return [a[0] for a in sorted(heap, key=lambda x: x[1])] \n```\n\nTime: `O(n * logk)`, space: `O(k)`\n\n----\n\n**Method 3: Quick Select**\n\n```java\n    public int[] maxSubsequence(int[] nums, int k) {\n        int n = nums.length;\n        int[] index = new int[n];\n        for (int i = 0; i < n; ++i) {\n            index[i] = i;\n        }\n        \n        // Use Quick Select to put the indexes of the \n        // max k items to the left of index array. \n        int lo = 0, hi = n - 1;\n        while (lo < hi) {\n            int idx = quickSelect(nums, index, lo, hi);\n            if (idx < k) {\n                lo = idx + 1;\n            }else {\n                hi = idx;\n            }\n        }\n        \n        // Count the occurrencs of the kth largest items\n        // within the k largest ones.\n        int kthVal = nums[index[k - 1]], freqOfkthVal = 0;\n        for (int i : Arrays.copyOf(index, k)) {\n            freqOfkthVal += nums[i] == kthVal ? 1 : 0;\n        }\n        \n        // Greedily copy the subsequence into output array seq.\n        int[] seq = new int[k];\n        int i = 0;\n        for (int num : nums) {\n            if (num > kthVal || num == kthVal && freqOfkthVal-- > 0) {\n                seq[i++] = num;\n            }\n        }\n        return seq;\n    }\n    \n    // Divide index[lo...hi] into two parts: larger and less than \n    // the pivot; Then return the position of the pivot;\n    private int quickSelect(int[] nums, int[] index, int lo, int hi) {\n        int pivot = index[lo];\n        while (lo < hi) {\n            while (lo < hi && nums[index[hi]] <= nums[pivot]) {\n                --hi;\n            }\n            index[lo] = index[hi];\n            while (lo < hi && nums[index[lo]] >= nums[pivot]) {\n                ++lo;\n            }\n            index[hi] = index[lo];\n        } \n        index[lo] = pivot;\n        return lo;\n    }\n```\n```python\n    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:\n        \n        # Divide index[lo...hi] into two parts: larger and less than \n        # the pivot; Then return the position of the pivot;\n        def quickSelect(lo: int, hi: int) -> int:\n            pivot = index[lo]\n            while lo < hi:\n                while lo < hi and nums[index[hi]] <= nums[pivot]:\n                    hi -= 1\n                index[lo] = index[hi]\n                while lo < hi and nums[index[lo]] >= nums[pivot]:\n                    lo += 1\n                index[hi] = index[lo]\n            index[lo] = pivot\n            return lo\n\n        n = len(nums)\n        index = list(range(n))\n        \n        # Use Quick Select to put the indexes of the \n        # max k items to the left of index array.\n        left, right = 0, n - 1\n        while left < right:\n            idx = quickSelect(left, right)\n            if idx < k:\n                left = idx + 1\n            else:\n                right = idx\n        \n        # Count the occurrencs of the kth largest items\n        # within the k largest ones.\n        kth_val, freq_of_kth_val = nums[index[k - 1]], 0\n        for i in index[ : k]:\n            if nums[i] == kth_val:\n                freq_of_kth_val += 1\n                \n        # Greedily copy the subsequence into output array seq.\n        seq = []\n        for num in nums:\n            if num > kth_val or num == kth_val and freq_of_kth_val > 0:\n                seq.append(num)\n                if num == kth_val:\n                    freq_of_kth_val -= 1\n        return seq\n```\nTime: average `O(n)`, worst `O(n ^ 2)`, space: `O(n)`.\n\n----\n\n***Please feel free to let me know if you can make the codes better.***
['Java', 'Python3']