673. The Largest Sum of a Value and Its Mirror
An array of EVEN length is given. Each position i is twinned with position n - 1 - i, and
the pair's twin sum is the total of the two values.
Print the largest twin sum.
5 4 2 1 -> 6 pairs (5,1) and (4,2)
4 2 2 3 -> 7 pairs (4,3) and (2,2)
1 2 3 4 5 6 -> 7
## The pairs are fixed, so nothing is chosen
Unlike most of this topic, the pointers are not searching. Every pair is decided by position alone, and the job is just to visit each pair once and keep the largest total.
i = 0, j = n-1, best = a[0] + a[n-1]
while i < j:
best = max(best, a[i] + a[j])
i += 1; j -= 1
Each step moves both pointers, so the loop runs n / 2 times and every pair is seen exactly
once.
## Why converging is the natural shape
Indexing by i and n - 1 - i in a single forward loop works equally well and is the same
computation. The converging form is written here because it says the structure out loud: the
array is being read from both ends at once, and the pairing is what the two pointers ARE.
When the same problem appears on a linked list, where n - 1 - i is not available, the
converging shape is the one that survives, using the fast-slow midpoint trick to find the
middle.
## The starting value
Seed best with the first pair, not with 0. Values may be zero and the array is never empty,
so the first pair is always available and always a legitimate answer.
Seeding at 0 happens to work when all values are non-negative, and it is the habit that fails on 579, 598 and 615. Seeding from real data is the version that transfers.
## Boundaries
Two values form one pair and that pair is the answer. All values equal give twice that value.
## Overflow
Values reach 10^9, so a sum reaches 2 * 10^9. Check that against the limit rather than
assuming: a signed 32 bit integer runs from -2147483648 to 2147483647, so
2000000000 and -2000000000 both FIT, with about seven percent to spare. This problem
has no overflow, and 64 bit accumulation here is margin rather than correctness.
## Cost
Time O(n). Space O(1).
Constraints - `2 ≤ n ≤ 200000` and `n` is even - `0 ≤ each value ≤ 10^9`
Input
The first line contains an even integer n.
The second line contains n integers.
Output
Print one integer, the largest twin sum.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.