# FINALSALE - Editorial

Author: yash_daga
Tester: jay_1048576
Editorialist: iceknight1093

TBD

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

A_1 + A_2 + \ldots + A_{i-1} + 2A_i

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)

 Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t-- > 0){
int n = sc.nextInt();
int[] sales = new int[n];
int max = Integer.MIN_VALUE;
int sum = 0;
for(int i = 0 ; i < sales.length ; i++){
sales[i] = sc.nextInt();
max = Math.max(sum + sales[i]*2 , max   );
sum += sales[i];
}
max = Math.max(sum , max);
System.out.println(max);
}


The answer can exceed the maximum value that int can store, so use long (or whatever 64-bit type Java has).
For reference, int can store values upto about 2\cdot 10^9, while long can store upto about 8\cdot 10^{18} (the exact values are 2^{31}-1 and 2^{63}-1).
In this problem the maximum answer is around 3\cdot 10^5 \times 10^9 \approx 3\cdot 10^{14} so int isn’t enough.

Because your final loop is printing each time the condition d + 2*b[i] > total is true. Say:

10 1 7 1

Total is 19

d + 2*b[i] is 20
when i = 0

d + 2*b[i] is 25
when i = 2

d + 2*b[i] is 20
when i = 3

You are printing the 3 of them. You should only print the maximal.

Plus, according the constraints, there’s a huge risk your variables overflow.

What you probably meant was:

#include <bits/stdc++.h>

#define int long long
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define V(x) vector
#define YES cout<<"YES"<<endl
#define NO  cout<<"NO"<<endl
#define SORT(vec) sort(vec.begin(), vec.end())
#define REVERSE(vec) reverse(vec.begin(), vec.end())

using namespace std;

signed main() {
FASTIO;

int test;
cin >> test;
//cin.ignore();
while(test--){

long long a,total=0,d=0,e=0;
cin>>a;
long long b[a];

FOR(i,0,a){
cin >> b[i];
total += b[i] ;
}

FOR(i,0,a){
if( d + 2*b[i]> total ){
//cout<<d + 2*b[i]<<endl ;
total = d + 2*b[i];
}
d += b[i];
}

cout << total << endl;
}
return 0;
}

1 Like