 Contest

Easy

# PREREQUISITES

Prefix Sums, Prefix-Postfix Maximum

# PROBLEM

Given two lists of N integers, a_1, a_2, \dots a_N and b_1, b_2, \dots b_N. For any pair (i, j) with i, j \in \{1, 2, \dots N\}, we define the segment from i to j, written as [i, j], to be i, i + 1, ..., j if i ≤ j and i, i + 1, ..., N, 1, 2, ...,j if i > j.
With each segment [i, j] we associate a special sum SSum[i, j] as follows:
if i=j, SSum[i,i] = a[i]
if i \neq j, SSum[i,j] = a_i + \displaystyle\sum_{k \in [i, j], k \neq i,j}{b_k} + a_j

Find the maximum value of SSum[i, j] over all segments [i, j].

# QUICK EXPLANATION

We have to take maximum of SSum[i,j] over all possible intervals [i,j]. There are three type of intervals- (i) i<j, (ii) i>j, (iii) i=j. We can fix j and find maximum value of SSum[i,j] by picking the best i in each case. This can be easily done using prefix sum of b, prefix-postfix maximum of (a[i]-prefixSumB[i]).

# EXPLANATION

Let’s consider three cases- (i) i<j, (ii) i>j, (iii) i=j.

## Case - 1: i<j

When i<j, SSum[i,j] can be written as following -

SSum[i,j] = a[i] + (b[i+1] + b[i+2] + ... + b[j-1]) + a[j]

Lets’s denote it in terms of prefix sums of b. Let pb[i] denote prefix sum of b till index i. Here the sum b[i+1] + b[i+2] + ... + b[j-1] can be written as pb[j-1] - pb[i]. Hence the above formula can be rewritten as -

SSum[i,j] = a[i] + pb[j-1] - pb[i] + a[j]

Now for any fixed j, maximum value of SSum can be denoted as SSumMax1(j).

SSumMax1(j) = a[j]+pb[j-1] + max(a[i]-pb[i]) for all i<j

Let c[j] denoate max(a[i]-pb[i]) for all i<=j
We can calculate c as following -

c = a-pb
c[j] = max(c[j-1], a[j]-pb[j]), for j>1

This array c can be calculated in linear time.
Now let’s write SSumMax1(j) in terms of c -

SSumMax1(j) = a[j]+pb[j-1] + c[j-1]

because term max(a[i]-pb[i]) for all i<j can be replaced as c[j-1].

So once we have arrays pb and c, we can calculate SSumMax1(j) in constant time. Then we can just loop through all j to find the maximum of SSumMax1(j).

## Case - 2: i>j

When i>j, SSum[i,j] can be written as following -

SSum[i,j] = (b + b + ... + b[j-1]) + a[j] + a[i] + (b[i+1]+b[i+2]+...+b[n])

Now let’s write it in terms of pb that is prefix sum of b as mentioned in case-1.

SSum[i,j] = pb[j-1] + a[j] + a[i] + (pb[n] - pb[i])

Now for any fixed j, maximum value of SSum can be denoted as SSumMax2(j).

SSumMax2(j) = pb[j-1] + a[j] + pb[n] + max(a[i]-pb[i]) for all i>j

Let d[i] denoate max(a[i]-pb[i]) for all i>=j
We can calculate d as following -

d[n] = a[n]-pb[n]
d[j] = max(d[j+1], a[j]-pb[j]), for j<n

This array d can be calculated in linear time.
Now let’s write SSumMax2(j) in terms of d -

SSumMax2(j) = pb[j-1] + a[j] + pb[n] + d[j+1]

because term max(a[i]-pb[i]) for all i>j can be replaced as d[j+1].

So once we have arrays pb and d, we can calculate SSumMax2(j) in constant time. Then we can just loop through all j to find the maximum of SSumMax2(j).

## Case - 3: i=j

When i=j, SSum[i,j] can be calculated as following -
SSum[i,j] = SSum[j,j] = a[j]

Now we can loop through all j and calculate maximum of SSum(j,j) in linear time.

Finally we have maximum from all three cases. And final answer is the maximum of all three cases.

# TIME COMPLEXITY

It takes linear time to calculate arrays pb, c, d. Also to calculate max of all three conditions, we loop through all j = 1 ...n, it takes linear time only. Hence overall time complexity is O(n).

# SOLUTION

C++ Code

/***************************************************

@author: vichitr
Compiled On: 24th Aug 2020

*****************************************************/
#include<bits/stdc++.h>
#define int long long
#define fast ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL)
using namespace std;

void solve(){
int n; cin>>n;
int a[n+1], b[n+1];
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) cin>>b[i];

int pb[n+1], c[n+1], d[n+2];

pb = c = d[n+1] = 0ll;

for(int i=1;i<=n;i++){
pb[i] = pb[i-1]+b[i];
}

c = a - pb;
for(int i=2;i<=n;i++){
c[i] = max(c[i-1], a[i] - pb[i]);
}

d[n] = a[n] - pb[n];
for(int i=n-1;i>0;i--){
d[i] = max(d[i+1], a[i] - pb[i]);
}

// case 3
int ans = *max_element(a+1, a+n+1);

// case 1
for(int j=2;j<=n;j++){
ans = max(ans, a[j]+pb[j-1]+c[j-1]);
}

// case 2
for(int j=1;j<n;j++){
ans = max(ans, pb[j-1]+a[j]+pb[n]+d[j+1]);
}

cout<<ans;
}

signed main()
{
fast;
int t=1;
// cin >>t;
for(int i=1;i<=t;i++)
{
solve();
}
return 0;
}

/*****************************

5
2 3 2 3 1
3 4 4 6 3

18

**************************/


Feel free to share your approach. In case of any doubt or anything is unclear please ask it in the comment section. Suggestions are welcome! 