Abstract / Summary

Given two integer arrays, find the highest possible sum by choosing elements from either array in order without reordering.

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 59% (40k+ submissions).

Typical patterns to solve this problem:

• Array
• Dynamic Programming

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 solves the “maximum spliced array” problem by treating the replacement of a sub-segment as a variation of the classic maximum subarray problem. It computes two candidate totals: one where a segment of the first array is swapped with the corresponding segment of the second array, and the opposite direction. The final answer is the larger of the two totals.

Key Steps

Defining the Kadane-style helper

A nested function implements Kadane’s algorithm to find the maximum sum of any contiguous sub-array in a list of differences. The helper maintains a running sum that is reset to zero whenever it becomes negative, ensuring that the best sum never drops below zero.

def subarray(diff):
    best = 0
    have = 0
    for d in diff:
        have = max(0, have + d)
        best = max(best, have)
    return best

Computing the gain for swapping nums1 → nums2

The first candidate is obtained by constructing a difference list where each element represents the gain obtained by replacing the element of nums1 with the element of nums2. The total sum of nums1 is then increased by the best gain found by the helper.

diff = [b - a for a, b in zip(nums1, nums2)]
one = sum(nums1) + subarray(diff)

Computing the gain for swapping nums2 → nums1

To evaluate the opposite direction, the same difference list is negated, turning a gain into a loss and vice-versa. The helper is invoked again, and the result is added to the sum of nums2.

diff = [-d for d in diff]
two = sum(nums2) + subarray(diff)

Selecting the optimal result

The method returns the larger of the two computed totals.

return max(one, two)

Edge Cases Handled

When every possible replacement would reduce the total sum, the helper’s reset-to-zero logic ensures that the best gain remains zero, effectively choosing not to perform any swap. This covers the situation where all entries in the difference list are negative.

If every entry in the difference list is positive, the helper accumulates the entire list, meaning the algorithm correctly chooses to replace the whole array.

When the two arrays are identical, the difference list consists of zeros; the helper returns zero, and both candidate totals equal the original sums, so the method returns the unchanged sum.

The code also works correctly for the minimal input size (a single element) because the zip operation and the subsequent loops each process exactly one element, and the Kadane helper still returns either the positive gain or zero.

Performance Optimizations

The solution performs a single linear pass to build the initial difference list, followed by a linear Kadane pass to obtain the maximum gain. The second candidate reuses the same list by negating its elements in place, avoiding allocation of a fresh list. Built-in sum and list comprehensions are employed for fast aggregation. The overall algorithm therefore runs in linear time with respect to the length of the input arrays while using only a constant amount of additional space beyond the input and the temporary difference list.

Imagine having two long train tracks made of colorful blocks. Each track has different numbers written on every block. The goal is to make one of the tracks have the biggest total sum of numbers possible by swapping a chunk of one track with a chunk from the other.

To start, the code looks at what happens if you take a part of the first track and replace it with a part from the second track. It figures out the difference between the blocks to see which swap gives the biggest boost to the total sum. It moves through the list piece by piece, keeping track of the best gain found so far if those blocks were swapped.

After finding the best swap to make the first track bigger, the code does the same thing for the second track. It flips the difference around to see how much the second track grows if it borrows a section from the first one.

Finally, the code compares the new total of the first track and the new total of the second track to see which one ended up with the biggest sum. It is just like picking the tallest tower after trying two different ways to build them.

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