STOCKMARKET - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: notsoloud
Tester: mridulahi
Editorialist: iceknight1093

DIFFICULTY:

948

PREREQUISITES:

None

PROBLEM:

Chef traded a stock for N days, and earned A_i on the i-th day (which could be negative).
What’s the maximum profit he could’ve earned if he skipped exactly one day?

EXPLANATION:

Suppose Chef skipped day i.
Then, his profit would be the sum of everything other than A_i, which equals

(A_1 + A_2 + \ldots + A_{i-1}) + (A_{i+1} + A_{i+2} + \ldots + A_N) \\ = (A_1 + A_2 + \ldots + A_{i-1}) + A_i + (A_{i+1} + A_{i+2} + \ldots + A_N) - A_i \\ = (A_1 + A_2 + \ldots + A_{i-1} + A_i + A_{i+1} + A_{i+2} + \ldots + A_N) - A_i \\

In other words, Chef’s profit equals the sum of all the elements of array A; minus A_i.
To maximize this, clearly we should subtract as small a value as possible, since the first term is a constant.
That is, the optimal choice is to subtract the minimum element.

So, the final answer is just \text{sum}(A) - \min(A).

TIME COMPLEXITY

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    print(sum(a) - min(a))