PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Authors: Lavish Gupta
Testers: Abhinav Sharma
Editorialist: Nishank Suresh
DIFFICULTY:
Easy
PREREQUISITES:
Prefix and suffix sums
PROBLEM:
The alternating sum of an array A is A_1 - A_2 + A_3 - \ldots + (-1)^{N-1}A_N. At most once, you can take an odd-sized subarray of A and move it to the end. What is the maximum possible alternating sum the final array can have?
EXPLANATION:
There are \mathcal{O}(N^2) odd-sized subarrays, so under the given constraints calculating the alternating sum when each one of them is moved to the end will be too slow.
Let’s analyze how the alternating sum changes when we move subarray [L, R] to the end. The array is now [A_1, A_2, \ldots, A_{L-1}, A_{R+1}, \ldots, A_N, A_L, \ldots, A_R].
Note that the array is effectively split into three parts - the prefix [1, L-1], the subarray [L, R], and the suffix [R+1, N].
Let’s look at the contribution of each of those parts to the alternating sum separately.
The prefix
The elements of the prefix don’t change their position whatsoever, and so the alternating sum of this part is A_1 - A_2 + A_3 - \ldots + (-1)^{L-2}A_{L-1} — exactly the same as its contribution to the alternating sum in the original array.
The suffix
The elements of the suffix [R+1, N] are moved such that A_{R+1} is at position L, A_{R+2} is at position L+1, and so on.
So, the alternating sum of this part is (-1)^{L-1}A_{R+1} + (-1)^L A_{R+2} + \ldots .
However, note that the length of the subarray is odd - i.e, R-L+1 is odd, which means that L and R have the same parity.
Thus, the above sum can also be written as (-1)^{R-1}A_{R+1} + (-1)^R A_{R+2} + \ldots + (-1)^{N-2}A_N.
However, alternating sum in the original array is (-1)^{R}A_{R+1} + (-1)^{R+1} A_{R+2} + \ldots — the sign of every element is flipped. Thus, this part contributes the negative of whatever it did to the original array.
The subarray
Let k = R-L+1 be the length of the subarray.
The elements of the subarray are moved such that they now start from position N-k+1 (because all the N-k elements outside the subarray are placed before it).
The alternating sum of this part is then (-1)^{N-k} A_L + (-1)^{N-k+1} A_{L+1} + \ldots (-1)^{N-k+R-L}A_R.
Now,
- If (-1)^{N-k} = (-1)^{L-1}, the alternating sum of this part is exactly the same as its alternating sum in the original array, because all the signs will remain the same.
- If (-1)^{N-k} \neq (-1)^{L-1}, the alternating sum of this part is the negative of its alternating sum in the original array, because all its signs flip.
When do these cases happen?
We know that k is odd, so N-k and L-1 have the same parity if and only if N and L have the same parity — equivalently, N and R have the same parity (because L and R have the same parity).
Putting it together, we know the following:
- The alternating sum of the prefix stays the same.
- The alteranting sum of the suffix is the negative of its alternating sum in the original array.
- The alternating sum of the subarray is either the same or the negative, depending only on the parity of the endpoints of the subarray.
This gives us the following idea: suppose we fix the right endpoint R of the subarray. Let’s try to find the optimal left endpoint L such that moving [L, R] to the end gives us as large an alternating sum as possible. Computing this for every 1 \leq R \leq N will give us the answer.
Note that we are dealing with prefix and suffix alternating sums, so it is useful to precompute those.
Let
Also note that once pref_i has been computed, the alternating sum of any subarray [L, R] can be obtained as pref_R - pref_{L-1}.
Now, fix the right endpoint R. There are two cases:
- Suppose R and N have the same parity. Then, for any 1\leq L \leq R (where R-L+1 is odd), the prefix [1, L-1] and the subarray [L, R] have the same alternating sum as the original array, while the suffix [R+1, N] has its alternating sum negated.
Putting this together, the total alternating sum is simply pref_R - suf_{R+1}, independent of choice of L. - Suppose R and N have different parities. Then, for any 1\leq L \leq R (where R-L+1 is odd), the prefix [1, L-1] has the same alternating sum, while the subarray [L, R] and the suffix [R+1, N] have their alternating sums negated.
The total alternating sum is then pref_{L-1} - suf_{R+1} - (pref_R - pref_{L-1}), which equals 2\cdot pref_{L-1} - pref_R - suf_{R+1}.
The latter two terms are independent of choice of L, so this expression is maximized when pref_{L-1} is maximized.
However, we already computed all the values of pref_i, so this is simple to do — just compute prefix maximums of the pref array. Remember that L and R must have the same parity (which is different from the parity of N in this case), so be sure to compute the maximums only over those indices whose parity matches the parity of N.
Once the prefix sums, suffix sums, and prefix maximums are computed, the answer for a given R can be found in \mathcal{O}(1). Thus, the algorithm as a whole runs in \mathcal{O}(N).
TIME COMPLEXITY:
\mathcal{O}(N) per test case.
SOLUTIONS:
Setter's Solution (C++)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
/*
------------------------Input Checker----------------------------------
*/
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
if(!(l <= x && x <= r))
{
cerr << l << ' ' << r << ' ' << x << '\n';
assert(1 == 0);
}
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
/*
------------------------Main code starts here----------------------------------
*/
const int MAX_T = 100000;
const int MAX_N = 100000;
const int MAX_SUM_N = 1000000;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
int sum_n = 0;
int max_n = 0;
int yess = 0;
int nos = 0;
int total_ops = 0;
ll z = 998244353;
ll dp[2500005] ;
void solve()
{
int n = readIntLn(3 , MAX_N) ;
sum_n += n ;
max_n = max(n , max_n) ;
ll arr[n] ;
for(int i = 0 ; i < n-1 ; i++)
arr[i] = readIntSp(1 , 1000000000) ;
arr[n-1] = readIntLn(1 , 1000000000) ;
ll suff[n] ;
int mult = 1 ;
if(n%2 == 0)
mult *= -1 ;
suff[n-1] = mult*arr[n-1] ;
mult *= -1 ;
for(int i = n-2 ; i >= 0 ; i--)
{
suff[i] = suff[i+1] + (mult * arr[i]) ;
mult *= -1 ;
}
ll ans = suff[0] ;
int len = 0 ;
for(int i = n-1 ; i >= 0 ; i--)
{
len++ ;
if(len%2 == 1)
{
continue ;
}
ll diff = (-2 * suff[i]) ;
ans = max(ans , suff[0] + diff) ;
}
cout << ans << endl ;
return ;
}
signed main()
{
// fast;
#ifndef ONLINE_JUDGE
freopen("inputf.txt" , "r" , stdin) ;
freopen("outputf.txt" , "w" , stdout) ;
freopen("error.txt" , "w" , stderr) ;
#endif
int t = 1;
t = readIntLn(1,MAX_T);
for(int i=1;i<=t;i++)
{
solve() ;
}
assert(getchar() == -1);
assert(sum_n <= MAX_SUM_N);
cerr<<"SUCCESS\n";
cerr<<"Tests : " << t << '\n';
cerr<<"Sum of lengths : " << sum_n << '\n';
cerr<<"Maximum length : " << max_n << '\n';
// cerr<<"Total operations : " << total_ops << '\n';
// cerr<<"Answered yes : " << yess << '\n';
// cerr<<"Answered no : " << nos << '\n';
}
Tester's Solution (C++)
#include <bits/stdc++.h>
using namespace std;
/*
------------------------Input Checker----------------------------------
*/
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
if(!(l <= x && x <= r))
{
cerr << l << ' ' << r << ' ' << x << '\n';
assert(1 == 0);
}
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
/*
------------------------Main code starts here----------------------------------
*/
const int MAX_T = 1e5;
const int MAX_N = 1e5;
const int MAX_SUM_LEN = 1e5;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ff first
#define ss second
#define mp make_pair
#define ll long long
int sum_len = 0;
int max_n = 0;
int yess = 0;
int nos = 0;
int total_ops = 0;
const ll MX=200000;
ll fac[MX], ifac[MX];
const ll mod = 998244353;
ll po(ll x, ll n ){
ll ans=1;
while(n>0){
if(n&1) ans=(ans*x)%mod;
x=(x*x)%mod;
n/=2;
}
return ans;
}
void solve()
{
int n = readIntLn(3,1e5);
sum_len += n;
ll a[n];
for(int i=0; i<n-1; i++) a[i] = readIntSp(1, 1e9);
a[n-1] = readIntLn(1, 1e9);
ll cur = 0;
for(int i=0; i<n; i++){
if(i&1) cur-=a[i];
else cur+=a[i];
}
ll o_mx = -1e18, e_mx =-1e18;
ll o_mn = 1e18, e_mn = 1e18;
ll ans = cur;
ll cur1 = 0;
for(int i=n-1; i>=0; i--){
if(i&1){
o_mx = max(o_mx, cur);
o_mn = min(o_mn, cur);
cur+=a[i];
cur1+=a[i];
if(n&1){
ans = max(ans, cur+cur1);
}
else{
// ans = max(ans, cur+cur1+2*(o_mx-cur));
}
}
else{
e_mx = max(e_mx, cur);
e_mn = min(e_mn, cur);
cur-=a[i];
cur1-=a[i];
if(n&1){
//ans = max(ans, cur+cur1+2*(e_mx-cur));
}
else{
ans = max(ans, cur+cur1);
}
}
}
cout<<ans<<'\n';
}
signed main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r" , stdin);
freopen("output.txt", "w" , stdout);
#endif
fast;
int t = 1;
t = readIntLn(1,1e5);
for(int i=1;i<=t;i++)
{
solve();
}
assert(getchar() == -1);
assert(sum_len<=1e6);
cerr<<"SUCCESS\n";
cerr<<"Tests : " << t << '\n';
cerr<<"Sum of lengths : " << sum_len << '\n';
cerr<<"Maximum length : " << max_n << '\n';
// cerr<<"Total operations : " << total_ops << '\n';
//cerr<<"Answered yes : " << yess << '\n';
//cerr<<"Answered no : " << nos << '\n';
}
Editorialist's Solution (Python)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
suf = 0
pref = 0
mxpref = 0
for i in range(n):
if i%2 == 0:
suf += a[i]
else:
suf -= a[i]
ans = suf
for i in range(n):
if i%2 == 0:
suf -= a[i]
pref += a[i]
else:
suf += a[i]
pref -= a[i]
if i%2 != n%2:
ans = max(ans, pref - suf)
mxpref = max(mxpref, pref)
else:
ans = max(ans, 2*mxpref - pref- suf)
print(ans)
).