Abstract / Summary

You must select operations to maximize total reward by choosing nodes and their parents under given constraints.

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 31% (100k+ submissions).

Typical patterns to solve this problem:

• Array
• Bit Manipulation
• Dynamic Programming
• Sorting

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 public method maxTotalReward. The method receives a list of integers, sorts it, and then uses a depth-first search with memoization to explore all possible ways of accumulating rewards. The recursion is driven by a helper function deeper that tracks the current total reward (have) and attempts to add each larger reward value in turn. The algorithm returns the maximum achievable sum of selected rewards.

Core Algorithm

The algorithm first sorts the input list, which guarantees that any later search for a value greater than the current total can be performed with binary search. The sorted order also ensures that the recursion only considers strictly increasing sequences of rewards, preventing duplicate work.

The recursive helper deeper receives the current accumulated reward (have). It uses bisect_right to locate the first reward value that exceeds have. From that position onward, it iterates through the remaining values, recursively calling itself with the new total (have + rewardValues[pos]). For each recursive call, it computes the candidate total as the sum of the chosen reward and the best result returned from deeper recursion. The maximum of these candidates is stored in best. An early-exit condition checks whether a recursive call returns zero, in which case the function can immediately return the larger of the current best and the global maximum reward (high).

The outer method simply initiates the recursion with a starting total of zero and returns the result.

Key Functions and Code Snippets

The sorting step establishes the order required for binary search:

rewardValues.sort()
size = len(rewardValues)
high = max(rewardValues)

The memoized recursive helper is defined with the @cache decorator, enabling automatic storage of previously computed results keyed by the have argument:

@cache
def deeper(have):
    # find next value greater than what we have
    pos = bisect_right(rewardValues, have)

    best = 0
    # try every bigger value, too
    while pos < size:
        next = deeper(have + rewardValues[pos])
        best = max(best, rewardValues[pos] + next)
        pos += 1

        # early exit
        if next == 0:
            return max(best, high)

    return best

The entry point invokes the helper with an initial total of zero:

return deeper(0)

Edge Cases Handled

When the input list contains a single element, sorting and max still produce valid values, and the binary search will locate the only element as the first candidate. The recursion will then evaluate the single possible addition and return that value as the maximum reward.

If the list includes duplicate values, the sorted order groups them together. The binary search (bisect_right) ensures that the next candidate is strictly greater than the current total, effectively skipping over duplicates that would not increase the total and avoiding redundant recursive paths.

When the current total already exceeds all remaining reward values, bisect_right returns a position equal to size. The while loop is bypassed, and best remains zero, causing the function to return zero. This return value is interpreted by the caller as an indication that no further reward can be added, triggering the early-exit condition in the previous stack frame.

The early-exit clause (if next == 0) captures the situation where a recursive branch cannot extend the total any further. In that case, the function immediately returns the larger of the best candidate found so far and the global maximum reward, ensuring that the algorithm does not waste time exploring deeper levels that cannot improve the result.

Performance Optimizations

Memoization via @cache eliminates repeated computation for identical have values. Since the recursion explores many overlapping subproblems, caching dramatically reduces the number of recursive calls, turning an exponential exploration into a tractable search.

Sorting the input list once at the beginning enables binary search (bisect_right) to locate the starting index for each recursive step in logarithmic time. This avoids a linear scan for the next larger reward and keeps the per-call overhead low.

The early-exit condition inside the loop provides a shortcut when a recursive call yields zero, meaning no further rewards can be added. By returning immediately with the best known value, the algorithm prunes entire branches of the search tree, preventing unnecessary deeper recursion.

The use of a global high variable (the maximum element in the list) allows the early-exit path to consider the possibility of taking the largest reward directly, without further recursion, when the remaining search cannot improve upon it. This contributes to faster convergence on the optimal total.

Imagine a game where you collect shiny red apples. Each apple has a number written on it, and you want to gather as many points as possible without ever picking up an apple with a number smaller than or equal to what you already have in your basket.

First, the code lines up all the apples from the smallest number to the biggest number so they are easy to look through. Then, the computer starts a little helper function to look at the apples one by one. It looks at the basket to see what the total points are right now and searches for the next apple that is just a bit bigger than the current total.

When the computer finds an apple that is big enough, it pretends to put that apple in the basket and starts the whole searching process over again with the new, bigger total. It keeps doing this for every possible apple it can find. Because there are a lot of apples, the computer remembers which choices it has already tried so it does not have to do the same work twice.

If the computer reaches a point where no more apples are bigger than the current total, it stops and tells everyone what the highest total number of points it could find is. It keeps track of the best score it sees at every step until it finishes checking all the different paths it could take. Once it has looked at every single possibility, it knows for sure which way to pick the apples results in the biggest prize.

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

not analyzed yet

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		Java	C++		Python	TS
	WalkCCC		Java	C++		Python
	leetcode.ca		Java	C++	Go	Python	TS
	Progiez		Java	C++		Python
github	charles-wangkai		Java
	everthis	JS
	fsq			C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
everthis	JavaScript
fsq	C++

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