354. The Double Helix - Maximum Sum Path Between Two Sequences

Two finite, strictly increasing sequences of integers are given. You may start at the very beginning of either sequence and walk forward through it. Whenever the value you're currently on also appears in the other sequence (a shared value), you may switch onto the other sequence from that point onward, or simply keep going on the one you're on. Find the maximum possible sum of every value visited along any such path, walking until you reach the end of whichever sequence you finish on.

Input: Four lines: n1; n1 space-separated strictly increasing integers; n2; n2 space-separated strictly increasing integers. Output: Print a single integer - the maximum sum achievable walking either sequence with switches allowed at shared values.

1 <= n1, n2 <= 10^5, both sequences strictly increasing

This elegant two-pointer merge-and-reset technique avoids ANY explicit backtracking or exponential branching at switch points - recognizing that shared values act as natural 'synchronization points' where the best-so-far from either path can be safely combined is the entire insight behind an efficient solution.

Walk along two strictly increasing sequences, switching between them at shared values, to maximize the total sum of values visited. Brute force: Try every possible sequence of switch-or-continue decisions at every shared value directly - this branches combinatorially at every switch point, impractical for large sequences without a systematic technique. Optimised: The KEY insight is that at any SHARED value, BOTH paths (whichever track you were on) are equally capable of having reached that point - resetting BOTH running sums to the LARGER of the two effectively 'merges' the best possible history from either track at that exact point, without needing to explicitly branch and explore both continuation choices separately.

Walk both sequences simultaneously with two pointers the way a merge-sort merge step does: at each step, advance whichever pointer sits on the smaller value, adding that value to a running sum kept separately for each sequence since the last shared value. Whenever both pointers land on the same (shared) value, add that value plus the larger of the two running sums to the final answer, then reset both running sums to zero and advance both pointers past the shared value. At the end, add whichever running sum is larger for the final unshared segment. This achieves the same total in the same linear time as the memoized recursion, but needs only a few running variables instead of a memo table or call stack, since it never revisits a position. Time: O(n1 + n2) Space: O(1) extra

Treat the state as a pair of pointers (position in sequence 1, position in sequence 2) and cache the best achievable sum from each distinct state the first time it is computed, since pointers only ever advance forward and never revisit earlier positions, the number of truly distinct states is bounded by the combined lengths of the two sequences rather than exploding combinatorially. This keeps the exact same recursive branching logic as the brute force but ensures every reachable state is solved only once, bringing the work down to linear in the sequence lengths. Time: O(n1 + n2) Space: O(n1 + n2)

At every position where the current sequence's value also appears in the other sequence, recursively branch into two possibilities: keep walking the current sequence, or jump to that matching position in the other sequence and continue from there, in both cases adding the values visited along the way; take the maximum total over all such recursive branches all the way to whichever sequence's end is reached. This correctly explores every possible path allowed by the rules, but every common value doubles the number of branches explored, so the number of paths considered grows exponentially with how many shared values exist. Time: O(2^c) where c is the number of shared values Space: O(n1 + n2) recursion stack

1. Walk both sequences with TWO POINTERS at once: always add the SMALLER of the two current values to that value's OWN running sum, and advance past it. 2. At a SHARED value, add it to BOTH running sums, then RESET both running sums to the LARGER of the two (either path could have reached this shared point) before continuing. 3. Once one sequence runs out, add every remaining element of the OTHER sequence to its running sum - the final answer is the LARGER of the two running sums.

Time: O(n1 + n2) - a single combined two-pointer pass through both sequences. Space: O(1) extra space beyond the two running sum trackers and two pointers.

Test sequences with no shared values at all (no switching possible, answer is just the larger sequence's own sum) and n1, n2 both at the 10^5 upper bound for O(n1+n2) two-pointer performance.

Be ready to explain WHY resetting both running sums to the MAXIMUM (not just picking one) at a shared value is correct - since a shared value is a genuine 'merge point' where either track's accumulated history becomes available to continue from, taking the maximum is exactly what preserves optimality without branching.