Maximum Sum Non-Adjacent Pairs
Given a list of N integers, find the maximum possible sum you can obtain by selecting pairs of adjacent elements, with the constraint that no two selected pairs can share an element. For example, if you select the pair (a[i], a[i+1]), you cannot select (a[i-1], a[i]) or (a[i+1], a[i+2]). If all possible sums are negative, the maximum sum is 0 (by selecting no pairs).
Input
The first line contains an integer N. The second line contains N space-separated integers.
Output
Print a single integer: the maximum sum achievable.
Constraints
1 <= N <= 200000. Each integer value is between -10^9 and 10^9.
Example 1
5 1 2 3 4 5
14
Possible non-overlapping pairs: (1,2) and (3,4) -> sum 10; (1,2) and (4,5) -> sum 12; (2,3) and (4,5) -> sum 14. The maximum sum is 14.
Example 2
5 10 -5 20 -3 15
27
Possible combinations: (10,-5) and (20,-3) sum 22; (10,-5) and (-3,15) sum 17; (-5,20) and (-3,15) sum 27. Maximum sum is 27.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
5 1 2 3 4 5
5 10 -5 20 -3 15