FINALSALE - Editorial


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

Author: yash_daga
Tester: jay_1048576
Editorialist: iceknight1093






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.


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}.

  • 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.


\mathcal{O}(N) per testcase.


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]
 Scanner sc = new Scanner(;
 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);

why this did not pass all testcases. please help someone

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() {

    int test;
    cin >> test;

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

            cin >> b[i];
            total += b[i] ;

            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