PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: raysh07
Editorialist: iceknight1093
DIFFICULTY:
Cakewalk
PREREQUISITES:
None
PROBLEM:
A shop has N items, the i-th costs C_i.
You want to buy at most two items from it - and if you buy two, the second one must have a not-smaller cost than the first.
Find the maximum amount you can spend.
EXPLANATION:
If we can only buy one item, there’s no restriction - so naturally we should buy whichever is the largest-valued item.
If we buy two items, we must ensure that the condition C_i \le C_j holds.
We can simply try all pairs (i, j) with i \lt j and take the largest value of C_i + C_j among pairs that satisfy the requisite condition.
This gives a simple quadratic solution which runs quickly for the given constraints.
It’s also possible to solve the second part in linear time, by remembering the largest value to the right of each index i (since after fixing i, it’s of course optimal to buy the largest C_j to its right if we can at all.)
TIME COMPLEXITY:
\mathcal{O}(N^2) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
ans = max(a)
for i in range(n):
for j in range(i+1, n):
if a[i] <= a[j]:
ans = max(ans, a[i] + a[j])
print(ans)