PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: notsoloud
Tester: jay_1048576
Editorialist: iceknight1093
DIFFICULTY:
928
PREREQUISITES:
None
PROBLEM:
Given an array A, find the largest possible sum of two distinct elements in it.
EXPLANATION:
Clearly, the answer is just the sum of the two largest different elements in A.
There are many ways to find these two elements.
Perhaps the simplest is as follows:
- First, run a loop to find the largest element of A, say M_1.
- Then, run another loop to find the largest element of A that’s not M_1, say M_2.
This can be done by simply ignoring all the occurrences of M_1 in the array.
The answer is then M_1 + M_2.
TIME COMPLEXITY
\mathcal{O}(N) per test case.
CODE:
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
m1, m2 = max(a), 0
for x in a:
if x != m1: m2 = max(m2, x)
print(m1 + m2)