# Help with Maximum sub-array (CDBSTR06)

I was solving the Maximum sub-array (CDBSTR06) problem. I do know how to implement Kadane’s algorithm to figure out the maximum sub-array sum but I am facing difficulty with
keeping track of the elements in that sub-array. Please help me with that. And once I figure out the elements how can I implement the instructions given as Note 1 and Note 2 in the problem statement?

refer to my commented solution
https://www.codechef.com/viewsolution/30544769
If you need help understanding, just ask.
the question doesn’t seem to be about kadane as it says you’re only allowed to use non negative numbers, so you need to split it into segments of positive numbers.

long max_so_far = a;
long current_max = a;
for(int i=1;i<size;i++)
{
current_max = max(a[i],current_max+a[i]);
max_so_far = max(max_so_far,current_max);
}
return max_so_far;

``````#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
#include <vector>
#define ll long long int
#define mp make_pair
#define pb push_back
#define vi vector<int>
using namespace std;
ll solve(){
int n;
cin>>n;
int seq[n];
ll maxsum=-1;
ll currsum=0;
int idxend=0;
int idxstart=0;
int curridxstart=0;
for(int i=0;i<n;i++){
cin>>seq[i];
if(seq[i]<0){
if(currsum>maxsum){ // check sum
idxstart=curridxstart;
idxend=i-1;
maxsum=currsum;
}
else if(currsum==maxsum){
if(i-curridxstart-1>idxend-idxstart){ //check length
idxend=i-1;
idxstart=curridxstart;
}
}  //we don't need to check for index since the smaller index will always be first
currsum=0;
curridxstart=i+1;
continue;   //we don't want to add seq[i]
}
currsum+=seq[i];
}
//if the answer is a suffix
if(currsum>maxsum){
idxstart=curridxstart;
idxend=n-1;
}
else if(currsum==maxsum){
if(n-curridxstart-1>idxend-idxstart){
idxend=n-1;
idxstart=curridxstart;
}
}
for(int i=idxstart;i<=idxend;i++){
cout<<seq[i]<<" ";
}
cout<<'\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >>t;
while(t--){
solve();
}
}
``````

I got an AC so I’m fairly sure I’m correct.
If you want to kadane’s simply change `seq[i]<0` to `currsum<0`

2 Likes

Thank you so much ! I’ll get back to you if I am unable to understand some part.