Maximum Sum of Pairs
Given an array A of N integers, find the maximum possible sum of A[i] + A[j] such that 0 <= i < j < N and A[i] <= A[j].
Input
The first line contains an integer N. The second line contains N space-separated integers representing the array A.
Output
Print a single integer, the maximum sum of such a pair.
Constraints
1 <= N <= 200000, 1 <= A[i] <= 10^9
Example 1
5 1 3 2 4 5
9
The pairs (1,3), (1,2), (1,4), (1,5), (3,4), (3,5), (2,4), (2,5), (4,5) are valid. The sums are 4, 3, 5, 6, 7, 8, 6, 7, 9. The maximum is 9 for (4,5).
Example 2
4 5 4 3 2
No valid pair found
No pair (i,j) with i < j satisfies A[i] <= A[j]. The answer should indicate no such pair exists, or be the minimum possible value if problem implies one exists. Here, no pair satisfies the condition.
Hints
Similar problems
- Subarray Sum Closest to TargetMedium
- Maximum Sum of Non-overlapping SubarraysMedium
- Maximum Average SubsegmentMedium
- Sum of Prefix ProductsEasy
- Minimize Maximum Difference of Grouped ElementsHard
- Longest Non-Decreasing SubsequenceHard
More topics: Prefix Sums problems, Binary Search problems, Dynamic Programming problems
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
5 1 3 2 4 5
4 5 4 3 2