380. Maximum Twin Sum of a Linked List

In a linked list of even length n, the i-th node (0-indexed) is the twin of the (n-1-i)-th node for 0 <= i < n/2. The twin sum is the sum of a node and its twin. Return the maximum twin sum.

Input: An even-length array of node values.

Output: Integer — the maximum twin sum.

Examples

Input: [5,4,2,1]
Output: 6
Explanation: Twin sums 5+1 and 4+2 are 6 each.

Input: [4,2,2,3]
Output: 7
Explanation: Max of 4+3 and 2+2.

Input: [1,100000]
Output: 100001
Explanation: Single twin pair.

Constraints

• 2<=n<=10^5
• n is even
• 0<=value<=10^5

Asked by