Abstract / Summary

Repeatedly merge the two smallest elements and replace them with their sum, then find the largest value remaining.

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 48% (80k+ submissions).

Typical patterns to solve this problem:

• Array
• Greedy

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 implementation defines a Solution class with a single method maxArrayValue. The method receives a list of integers and returns the greatest value that can be obtained by repeatedly merging adjacent elements while preserving a non-decreasing order of the merged segment. The algorithm proceeds in two phases: an initial scan to obtain the maximum element, followed by a right-to-left traversal that builds candidate sums whenever the current element does not break the non-decreasing property.

Key Steps

Initial maximum extraction

result = max(nums)

The first statement records the largest individual element. This value serves as a baseline because any valid merged segment must be at least as large as the biggest single entry.

Preparation for the reverse scan

increasing = -inf

A sentinel value of negative infinity is used to indicate that no segment has been started yet. This choice guarantees that the first element encountered in the reversed order will always start a new segment.

Reverse iteration and segment construction

for n in reversed(nums):
    if n <= increasing:
        increasing += n
        result = max(result, increasing)
    else:
        increasing = n

The loop walks through the list from the end toward the beginning. For each element n:

• If n is less than or equal to the current accumulated sum (increasing), the element can be merged into the existing segment without violating the non-decreasing requirement. The sum is updated in place, and the global result is refreshed if this new sum exceeds the previous best.
• If n is larger than increasing, the non-decreasing condition would be broken by merging, so a fresh segment is started with n as its sole member.

Final result

return result

After the traversal, result holds the maximum value observed among all individual elements and all merged segments that respect the ordering constraint.

Edge Cases Handled

When the input list consists of a single element, the initial max(nums) yields that element, and the reverse loop processes the same value, leaving result unchanged.

If the list is strictly decreasing (each element smaller than the one to its right), every element satisfies the n <= increasing condition after the first iteration, causing the algorithm to accumulate the entire array into a single sum. The final result therefore becomes the total of all elements.

Conversely, for a strictly increasing list, each element fails the n <= increasing test, prompting the algorithm to reset the segment at every step. In this scenario, result remains the maximum individual element, which is the correct answer because no merging can improve the value without breaking the required order.

The use of -inf as the initial sentinel ensures that the first element processed in the reversed order always initiates a segment, even when the list contains negative numbers. The comparison n <= increasing correctly handles negative values, allowing the algorithm to merge them when appropriate.

Performance Optimizations

The solution performs a single linear pass after the initial max call, avoiding any nested loops or auxiliary data structures. By iterating in reverse, it can decide on-the-fly whether to extend the current segment or start a new one, eliminating the need for additional bookkeeping arrays.

All updates to the running sum and the global maximum are done in constant time, and the algorithm maintains only two scalar variables (result and increasing) besides the input list, achieving minimal memory overhead. The reliance on Python’s built-in max function for both the initial extraction and the per-iteration comparison leverages highly optimized C-level implementations, contributing to overall speed.

Imagine a line of numbered blocks standing in a row. The goal is to see how big the blocks can become if they follow a special set of rules. This process starts by looking at the line from the very last block all the way back to the first one.

Think of a small basket that starts out empty. As the journey moves backward down the line, each block gets picked up. If the block is smaller than or the same size as the ones already in the basket, it gets squished together with them to make a new, bigger block. If the block is bigger than what is currently in the basket, it takes the place of everything inside, becoming the new champion. All the while, a mental note is kept to remember where the biggest block was ever seen. It is like a game of gathering pieces and making them stronger, keeping track of the largest one found during the entire trip from the back to the front.

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

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

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