Help with Maximum sub-array (CDBSTR06)

general
,
1

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?

2

Is it this question? Please link the question from next time.

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.

3

long max_so_far = a[0];
long current_max = a[0];
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;

DRY RUN THIS CODE THIS WILL HELP YOU?
KADANE ALGO.

4

Thanks @everule1 for the link but on clicking the link to your solution it gives 403 (Access Denied). What should I do? And I think that it is actually about Kadane’s algorithm with the twist being in storing the starting and ending index of the sub-array and then keeping the longest sub-array with the maximum sum? How should I go about implementing this? Please help.

5 
#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
6

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