# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author:* yash_daga

*jay_1048576*

**Tester:***iceknight1093*

**Editorialist:**# DIFFICULTY:

TBD

# PREREQUISITES:

None

# PROBLEM:

Chef knows that his store’s projected sales on the i-th day is A_i.

He can also close down his store on some day, doubling the sales on that day - but this will cause him to lose out on sales of all the following days.

Find the maximum possible sales he can achieve by acting optimally.

# EXPLANATION:

If Chef chooses to close down his store on day i, his sales will be exactly

Unfortunately, computing this directly using a loop for each i will result in an \mathcal{O}(N^2) algorithm, which is too slow.

To optimize it, notice that for each index, you only need the loop to know the sum of all the elements before it; so instead of recomputing this from scratch each time, it can be computed a bit more cleverly.

Let P_i denote the sum of all the elements before index i, that is P_i = A_1 +A _2 + \ldots + A_{i-1}.

Then,

- P_1 = 0; and
- For i\gt 1, we have P_i = P_{i-1} + A_{i-1}, since P_{i-1} includes the sum of all the elements upto index i-2 already!

This allows for the array P to be computed using a single `for`

loop, since it only needs a single loop from 1 to N.

Once array P is computed, the answer is just the maximum value of P_i + 2A_i across all i which is easy to compute, again with a single loop.

Note that the array P computed here is essentially just the prefix sum array of A (shifted by one step), which is something that comes up *very* often when solving problems.

# 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()))
ans = 0
before = 0
for i in range(n):
ans = max(ans, before + 2*a[i])
before += a[i]
print(ans)
```