DoubleHelix — maximum sum path across two arrays
Problem
Two sorted arrays share some values ("intersection points"). You walk through one array from left to right, and at any shared value you may switch to the other array and continue from that value. Return the largest possible sum of the values you visit.
Example 1
Input: a = [3, 5, 7, 9, 20, 25, 30, 40, 55, 56, 57, 60, 62], b = [1, 4, 7, 11, 14, 25, 44, 47, 55, 57, 100] Output: 450
Also asked as: DoubleHelix SPOJ
Test cases
Case 1
Input: [3,5,7,9,20,25,30,40,55,56,57,60,62], [1,4,7,11,14,25,44,47,55,57,100] Expected: 450
Case 2
Input: [2,3,7,10,12], [1,5,7,8] Expected: 35
Case 3
Input: [1,2,3], [4,5,6] Expected: 15
Case 4
Input: [], [] Expected: 0
View solutionHide solution1 approach
1. Merge with segment sums, switch at common elements
Time O(n + m)Space O(1)
Walk both sorted arrays with two pointers, accumulating a running sum for each. At a common value, add the larger of the two running sums to the total and reset both.
function doubleHelix(a, b) { let i = 0, j = 0, sumA = 0, sumB = 0, total = 0; while (i < a.length && j < b.length) { if (a[i] < b[j]) sumA += a[i++]; else if (a[i] > b[j]) sumB += b[j++]; else { total += Math.max(sumA, sumB) + a[i]; sumA = sumB = 0; i++; j++; } } while (i < a.length) sumA += a[i++]; while (j < b.length) sumB += b[j++]; return total + Math.max(sumA, sumB);}