LARGESECOND - Editorial

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)