 CYCLCSUM - Editorial

Author: Prashant Shishodia
Tester: Raja Vardhan Reddy
Editorialist: Akash Bhalotia

Easy-Medium

Max-Sum Subarray

PROBLEM:

Find the maximum sum subarray of an array, for each of its N left rotations.

HINTS:

Not the full solution. Just some hints to help you if you are stuck at some point. As soon as you encounter a hint that you had not thought of, go back to solving the problem.

Hint 1:

Imagine that after i rotations, the original array is divided into two parts:

Part 1: A_i, A_{i+1}, A_{i+2}, \ldots A_N, and
Part 2: A_1, A_2, A_3 \ldots A_{i-1}.

Hint 2:

The maximum sum subarray will either be in Part 1 or in Part 2, or in some part obtained after joining Part 1 with Part 2.

Hint 3:

The maximum sum subarrays present in Part 1 and Part 2 can be computed using Kadane’s algorithm, for every index.
For Part 2, we can use it in the normal way, but for Part 1, we need to reverse the array, and then compute it.
For the maximum sum subarray obtained by joining Parts 1 and 2, we need to find the maximum sum suffix starting at or after every index and the maximum sum prefix ending at or before every index. The maximum sum suffix of Part 1 added with the maximum sum prefix of Part 2 will give us the maximum sum subarray which can be obtained on combining Parts 1 and 2, after every rotation.

QUICK EXPLANATION:

show

For every index i, find the maximum sum subarray ending at or before this index, the maximum sum subarray starting at or after this index, the maximum sum prefix ending at or before this index and the maximum sum suffix starting at or after this index.

The answer, after i rotations, will be the maximum of the maximum sum subarray starting at or after index i, the maximum sum subarray ending at or before index (i-1), and the sum of the maximum sum suffix starting at or after index i with the maximum sum prefix ending at or before index (i-1).

EXPLANATION

show

We need to find the maximum sum of a contiguous subsequence. This is the same as finding the maximum sum subarray, which can be learnt from here.

However, we’ll be rotating the array too. How to deal with this?

Let us visualise the rotations in a particular way:
After i rotations, the sequence will be A_i, A_{i+1}, A_{i+2}, \ldots A_N, A_1, A_2, A_3 \ldots A_{i-1}.
We need to find the max-sum subarray of this sequence.

Imagine this sequence is made up of two parts,
Part 1: A_i, A_{i+1}, A_{i+2}, \ldots A_N, and
Part 2: A_1, A_2, A_3 \ldots A_{i-1}.

The max-sum subarray of this sequence will be either:

1. In Part 1, or
2. In Part 2, or
3. The subarray obtained by joining some suffix of Part 1 with some prefix of Part 2.

We shall compare these three for every rotation, and output the max of them as the answer. But first, let’s see how we can compute them efficiently.

Let’s first see how to compute the max-sum subarray for the Part 2's of the sequence obtained after every rotation. So, for every index i, we need to find the max-sum subarray which ends at or before this index, in the sequence A_1, A_2, A_3 \ldots A_{i-1}.
For every array index i, Kadane’s algorithm enables us to compute the max-sum subarray value, if the subarray ends at this index.

//MSS[i] = Maximum sum subarray ending at position i
//(Element at position i is also included here)

MSS=a;
for(i=2;i<=N;i++)
MSS[i]=max(MSS[i-1]+a[i], a[i]);

MSS ending at position i will either be an extension of MSS ending at position (i-1), or will begin at position i.

However, this only gives us the MSS (max-sum subarray) ending at position i. To obtain the MSS present in every Part 2 sequence, we actually need the MSS ending at or before index i, as after i rotations, the MSS can lie anywhere in Part 2.

Let the start of the MSS in Part 2 be l, and end be r. After i rotations, MSS in Part 2 can lie anywhere in between the end-points : (1 \le l \le r \le i).

How can we obtain the MSS ending at or before every index i, if we know the value of MSS ending at every i?

show

It’s a simple extension of Kadane’s algorithm

// MSSPart2[i] = Maximum sum subarray ending at or before index i
// (Can be anywhere 1<=l<=r<=i in Part 2)

MSSPart2=MSS;
for(i=2;i<=N;i++)
MSSPart2[i]=max(MSSPart2[i-1],MSS[i]);

MSS ending at or before index i will be the maximum of the MSS ending at or before index (i-1), and the MSS ending at index i.

Thus, once we have the value of the maximum sum subarray ending at or before every index i, we can easily find the MSS present in Part 2 of the sequence after every rotation.

Now, let’s look at the MSS present in Part 1 after every rotation.
After i rotations, Part 1 will consist of the sequence: A_i, A_{i+1}, A_{i+2}, \ldots A_N

The MSS of Part 1 can be anywhere (i \le l \le r \le N) in Part 1.
So, to find the MSS present in Part 1 after every rotation, we need to find the MSS starting at or after index i.

The method to do this is the same as the one used to find the MSS present in Part 2 after every rotation, we just need to iterate backwards from N to 1, instead of the other way.

show
// MSS[i] = Maximum Sum Subarray starting at index i
// (Element at index i needs to be included. MSS[i] starts from here)

MSS[N] = a[N];
for(i=N-1;i>=1;i--)
MSS[i]=max(MSS[i+1]+a[i],a[i]);

// MSSPart1[i] = Maximum sum subarray starting at or after index i.
// (MSSPart[i] can be anywhere i<=l<=r<=N)

MSSPart1[N] = MSS[N]
for(i=N-1;i>=1;i--)
MSSPart1[i]=max(MSSPart1[i+1],MSS[i]);

MSS starting at or after index i will be the maximum of the MSS starting at or after index (i+1), and the MSS starting at index i.

Now, we just need to find the MSS which can be obtained by concatenating some suffix of Part 1 with some prefix of Part 2, after every rotation.

These prefixes and suffixes after i rotations are actually the maximum sum prefix (MSPref) ending at or before the index, and the maximum sum suffix (MSSuf) starting at or after the index.

Maximum Sum Prefix

A prefix of an array is a subarray which starts at index 1.

Maximum sum prefix, ending at at or before index i, is some prefix the array ending at index, say, p (1 \le p \le i) such that the sum of array elements from indices 1 to p is greater than the sum of array elements from index 1 to any other index \le i.

For example, consider the sequence:
2, 3, -1, 4, -5, 10, 15, -20, 7

Let’s say, we need to find the maximum sum prefix ending at or before element -5 in the array (index 5).
This will be = 8. (2+3-1+4).

If we want to find the MSPref ending at or before element 10 in the array (index 6),
it will be = 13. (2+3-1+4-5+10).

// MSPref[i] = Maximum sum prefix ending at or before index i

MSPref = a;
sum = a;

for(i=2;i<=N;i++)
{
sum + = a[i];
MSPref[i] = max(MSPref[i-1], sum);
}

The MSPref ending at or before index i will be the maximum of the MSPref ending at or before index (i-1) and the sum of all elements from the starting index to index i.

Maximum Sum Suffix

MSSuf is similar to the MSPref.

A suffix of an array is a subarray that ends at index N.

Maximum sum suffix, starting at at or after index i, is some suffix the array starting at index, say, s (i \le s \le N) such that the sum of array elements from indices s to N is greater than the sum of array elements of any other suffix starting at or after i.

// MSSuf[i] = Maximum sum suffix starting at or after index i

MSSuf[N] = a[N];
sum = a[N];

for(i=N-1;i>=1;i--)
{
sum + = a[i];
MSSuf[i] = max(MSSuf[i+1], sum);
}

The MSSuf starting at or after index i will be the maximum of the MSSuf starting at or after index (i+1) and the sum of all elements from indices i to N.

Once we have the MSPref ending at or before every index i, we can easily find the MSPref in Part 2 after every rotation.
Similarly, if we have the MSSuf starting at or after every index i, we can compute the MSSuf in Part 1 after every rotation.

The sum of MSSuf of Part 1 and MSPref of Part 2 will make up the MSS which can be obtained on joining Part 1 with Part 2, after every rotation.

Thus, to solve the problem,

1. Imagine the original array (without any rotations) is cut into two parts after every rotation.
2. Compute the Maximum sum subarray for the two parts, after every rotation, as described above.
3. Compute the maximum sum prefix ending at or before each index i, and the maximum sum suffix starting at or after each index i. The MSPref of Part 2, added with the MSSuf of Part 1 will give us the MSS which can be obtained by joining Part 1 and 2 after every rotation.

TIME COMPLEXITY:

show

The time complexity is: O(N)

Why?

Computing max-sum subarray, max-sum prefix array, max-sum suffix array, etc. all take O(N), and are independent of each other.
Thus, the time complexity is O(N).

SOLUTIONS:

Setter
#include <bits/stdc++.h>

using namespace std;

const int N = 500000;
const int T = 100;
const int VAL = 1000000000;
const long long INF = 1e17;
long long a[N + 10], mxPrefix[N + 100], mxSuffix[N + 100], prefix[N + 100], suffix[N + 100];

int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);

int t; cin>>t;
if(!(t >= 1 && t <= T)){
cout<<"Test cases "<<t<<". Exiting... \n";
assert(t >= 1 && t <= T);
}
int sumOfN = 0;

while(t--){
int n; cin>>n; 	sumOfN += n; assert(n >= 1 && n <= N);
// ith circular shift is A[i + 1], A[i + 2], ... A[n], A, .. A[i]
for(int i = 1;i <= n; ++i){
cin>>a[i]; assert(abs(a[i]) <= VAL);
}

mxPrefix = prefix = mxSuffix[n + 1] = suffix[n + 1] = -INF;
long long sum = 0, mx_till_here = -INF;
for(int i = 1; i <= n; ++i){
sum += a[i];
mx_till_here = max(mx_till_here + a[i],a[i]);
mxPrefix[i] = max(mxPrefix[i - 1], mx_till_here);
prefix[i] = max(prefix[i - 1], sum);
}

sum = 0, mx_till_here = -INF;
for(int i = n; i >= 1; --i){
sum += a[i];
mx_till_here = max(mx_till_here + a[i], a[i]);
mxSuffix[i] = max(mxSuffix[i + 1], mx_till_here);
suffix[i] = max(suffix[i + 1], sum);
}

for(int i = 0; i < n; ++i){
// answer in the ith shift.
long long ans = mxSuffix[i + 1];
ans = max(ans, mxPrefix[i]);
ans = max(ans, prefix[i] + suffix[i + 1]);
cout<<ans<<" ";
}
cout<<"\n";
}
assert(sumOfN <= N);
return 0;
}
Tester
//raja1999

//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")

#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//setbase - cout << setbase (16)a; cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 <<endl;prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val

using namespace std;
using namespace __gnu_pbds;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define int ll

typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;

//std::ios::sync_with_stdio(false);
const int N=500005;
int a[N],suf[N],pref[N],maxs[N],maxp[N],ans[N],sufans[N],maxanss[N],maxansp[N];
main(){
std::ios::sync_with_stdio(false); cin.tie(NULL);
int t;
cin>>t;
//t=1;
while(t--){
int n,i,res;
cin>>n;
for(i=0;i<n;i++){
cin>>a[i];
pref[i]=i>0?pref[i-1]+a[i]:a[i];
maxp[i]=i>0?max(maxp[i-1],pref[i]):pref[i];
}
for(i=n-1;i>=0;i--){
suf[i]=i<n-1?suf[i+1]+a[i]:a[i];
maxs[i]=i<n-1?max(maxs[i+1],suf[i]):suf[i];
}
for(i=0;i<n;i++){
ans[i]=i>0?max(ans[i-1]+a[i],a[i]):a[i];
maxansp[i]=i>0?max(maxansp[i-1],ans[i]):ans[i];
}
for(i=n-1;i>=0;i--){
sufans[i]=i<n-1?max(sufans[i+1]+a[i],a[i]):a[i];
maxanss[i]=i<n-1?max(maxanss[i+1],sufans[i]):sufans[i];
}
for(i=0;i<n;i++){
res=maxanss[i];
if(i!=0){
res=max(res,maxansp[i-1]);
res=max(res,maxs[i]+maxp[i-1]);
}
cout<<res<<" ";
}
cout<<endl;

}
return 0;
}
Editorialist
//created by Whiplash99
import java.io.*;
import java.util.*;
class A
{
private static final long INF=(long)(1e17);
public static void main(String[] args) throws IOException
{

int i,N;

StringBuilder sb=new StringBuilder();

while(T-->0)
{
int a[]=new int[N+1];
for(i=0;i<N;i++)
a[i+1]=Integer.parseInt(s[i]);

long maxPref[]=new long[N+2];
long maxSuf[]=new long[N+2];
long maxPart1[]=new long[N+2];
long maxPart2[]=new long[N+2];
long sum,maxEndingHere;

maxPref=maxPart1=maxSuf[N+1]=maxPart2[N+1]=-INF;
sum=0; maxEndingHere=-INF;
for(i=1;i<=N;i++)
{
sum+=a[i];
maxEndingHere=Math.max(maxEndingHere+a[i],a[i]);

maxPart1[i]=Math.max(maxPart1[i-1],maxEndingHere);
maxPref[i]=Math.max(maxPref[i-1],sum);
}

sum=0; maxEndingHere=-INF;
for(i=N;i>=1;i--)
{
sum+=a[i];
maxEndingHere=Math.max(maxEndingHere+a[i],a[i]);

maxPart2[i]=Math.max(maxPart2[i+1],maxEndingHere);
maxSuf[i]=Math.max(maxSuf[i+1],sum);
}

for(i=0;i<N;i++)
{
long ans=maxPart1[i];
ans=Math.max(ans,maxPart2[i+1]);
ans=Math.max(ans,maxPref[i]+maxSuf[i+1]);

sb.append(ans).append(" ");
}
sb.append("\n");
}
System.out.println(sb);
}
}

Feel free to share your approach if it differs. You can ask your doubts below. Please let me know if something’s unclear. I would LOVE to hear suggestions 3 Likes

I have created a array twice the size of the given one and initial the extra elements of array to zero .
Then kadane algo and then swap for every time…

2 Likes

Still not working

why the tester’s solution is not working without these #define and typedef

It can also be solved using segment tree.

1 Like

that will not work buddy its time complexity will be t*(n-1)n = tn^2
t for no of test cases n*n bcs you will apply kadanes algo n-1 times

This is what I did - querying [k,k+n) for each k. This has complexity O(N*log N) but passed here: Solution: 55331805 | CodeChef