Get the Maximum Score - Video Solutions

Problem Overview: You are given two sorted arrays. You can traverse either array from left to right and switch to the other array whenever both contain the same value. The goal is to maximize the total sum of visited elements.

Approach 1: Two Pointer Greedy Traversal (O(n + m) time, O(1) space)

This approach exploits the fact that both arrays are sorted. Use two pointers to iterate through nums1 and nums2 simultaneously. Maintain two running sums representing the score collected along each array segment since the last intersection. When the values differ, advance the pointer with the smaller value and add it to its running sum. When both values match, you reach a switch point. Add the larger of the two running sums plus the common value to the final answer, then reset both sums. This greedy decision works because any path before the intersection is independent of future choices. Continue until both arrays are processed, then add the larger remaining segment sum. This method relies on sequential scanning using two pointers and simple arithmetic, making it both optimal and memory efficient.

Approach 2: Dynamic Programming with Memoization (O((n + m) log(n + m)) time, O(n + m) space)

Dynamic programming models the problem as choices between continuing in the same array or switching when encountering a shared value. Preprocess both arrays with a map from value to index so you can jump between arrays at intersections. Define a recursive state dp(i, arr) representing the maximum score starting from index i in a specific array. The recurrence accumulates values while moving forward and optionally jumps to the corresponding index in the other array when a shared element appears. Memoization stores computed states to avoid repeated work. This approach frames the problem using dynamic programming over indices and transitions. It is conceptually useful but less efficient than the linear greedy solution.

The key observation behind the optimal solution is that segments between intersections are independent. You only need to choose the larger accumulated sum before switching paths. That converts what looks like a path optimization problem into a simple greedy merge process across two arrays.

Recommended for interviews: The two pointer greedy approach is what interviewers expect. It demonstrates that you recognize the sorted structure and reduce the problem to linear traversal. Mentioning a DP formulation shows deeper understanding, but implementing the O(n + m) two-pointer solution proves strong algorithmic instincts.