416. Maximum Sum Path in Two Sorted Linked Lists

Given two sorted linked lists that may share some common nodes (equal values), find the maximum sum path from the start to the end. You may switch from one list to the other only at common nodes. The maximum sum is obtained by, between consecutive common values, taking whichever list's segment has the larger sum. Lists are given as sorted arrays. Return the maximum sum. Input: '[l1], [l2]'.

Input: '[l1], [l2]'.

Output: Integer — the maximum path sum.

Examples

Input: [1,3,30,90,120,240,511], [0,3,12,32,90,125,240,249]
Output: 1014
Explanation: Switch at common values 3, 90, 240 for the larger segments.

Input: [1,3,5,7], [2,4,6,8]
Output: 36
Explanation: No common nodes; take the larger total.

Input: [1,2,3], [1,2,3]
Output: 6
Explanation: Identical lists.

Constraints

• 0<=n,m<=10^4
• both sorted ascending

Asked by