Abstract / Summary

Find the largest sum of any k length sequence that keeps the original order of elements.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 57% (300k+ submissions).

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a Solution class with a single method maxSubsequence. The method receives a list of integers nums and an integer k, and returns a subsequence of length k that has the maximum possible sum while preserving the original relative order of the selected elements. The algorithm proceeds in three logical phases: pairing each element with its index, extracting the k largest elements based on value, and finally re-ordering the chosen elements to match their original positions.

Step 1: Pair values with indices

The first operation creates a list of tuples where each tuple contains a number from nums and its corresponding index. This pairing is essential because the later sorting steps need to keep track of where each element originally appeared.

pos = [(n, i) for i, n in enumerate(nums)]

By using enumerate, the code captures the index i alongside the value n. The resulting list pos retains a one-to-one mapping between values and their positions, which is later used to both select the largest values and to restore order.

Step 2: Select the k largest elements

The second phase sorts the list of (value, index) tuples in descending order of the value component. Python’s default tuple comparison first looks at the first element, so sorting with reverse=True yields the elements with the highest numeric values at the front of the list. The slice [:k] then extracts exactly k entries.

largest = sorted(pos, reverse=True)[:k]

Because each tuple still carries its original index, the selection retains the necessary positional information for the final ordering step.

Step 3: Restore original order

After identifying the k largest elements, the algorithm must return them in the order they appeared in the original array. To achieve this, it creates a new list of (index, value) tuples from largest and sorts this list by the index component in ascending order.

ordered = sorted([(i, n) for n, i in largest])

The final list comprehension extracts only the values, discarding the indices, and yields the required subsequence.

return [n for i, n in ordered]

Edge Cases Handled

The code implicitly handles several boundary conditions without explicit checks. When k equals the length of nums, the slice [:k] returns the entire sorted list, and the subsequent ordering step restores the original sequence, effectively returning a copy of the input. If k is zero, the slice yields an empty list, and the final comprehension returns an empty list as well, which is a sensible result for a zero-length subsequence. The use of sorted on an empty list is well defined, so no error is raised. Additionally, duplicate values are treated correctly because the tuple includes the original index; ties are broken by the index order during the initial descending sort, ensuring deterministic selection of the earliest occurrences among equal values.

Performance Optimizations

The implementation leverages Python’s built-in sorted function, which is highly optimized in C and provides stable sorting. By sorting the entire list of (value, index) pairs once and then slicing the first k elements, the algorithm avoids repeated scans or manual heap management. The second sort operates on a list of size k, which is typically much smaller than the original list, reducing the cost of the final ordering step. The use of list comprehensions for both the pairing and the extraction phases minimizes overhead compared to explicit loops, resulting in concise and efficient execution.

Imagine you have a big bag filled with numbered blocks, and you want to pick out a few to keep. The goal is to find the biggest numbers in that bag.

First, look at every block and write down its number along with a tiny secret tag that says where it started in the line. This helps keep track of which block is which, even if you move them around later.

Next, line all the blocks up from the biggest number to the smallest number. Since you only want to keep a certain amount, pick the top ones from the front of this new line. These are the biggest blocks you have found.

Now, take those special blocks and look at their secret tags to see where they used to be in the original line. Put them back in that same order so they are standing just like they were at the start. Finally, just read the numbers off the blocks standing in their original spots.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: loglinear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python			Java				TS
	WalkCCC	C++	Python			Java
	leetcode.ca	C++	Python			Java		Go	Rust	TS
	Progiez	C++	Python			Java
github	black-shadows	C++
	charles-wangkai					Java
	fartem			Ruby
	fsq	C++
	JoshCrozier				JS
	lkwq007		Python
	suxrobGM						C#
	trung-hn		Python
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
fartem	Ruby
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
suxrobGM	C#
trung-hn	Python

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality