Kadane's algorithm for printing the elements of the maximum subarray found?

Question

I modified the Kadane's algorithm to the following so that it works even in the case wherein I have all negative numbers in the array.

//Largest Sum Contiguous Subarray
#include <iostream>
#include <map>
#include <vector>
#include <string>
#include <utility>
#include <algorithm>

using namespace std;

#define ll long long
#define pb push_back
#define mp make_pair
#define F(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define RF(i,a,b) for(int i = (int)(a); i >= (int)(b); i--)
#define SIZE 100000

int main (void)
{
    vector<int> myvec;
    int arr[SIZE];
    int index[SIZE] = {0};
    int n;
    cin>>n;
    F(i,0,n)
    {
        cin>>arr[i];
    }
    int maxendinghere = arr[0];
    int maxsofar = arr[0];
    F(i,1,n)
    {
        if (arr[i] > (arr[i]+maxendinghere))
            myvec.pb(i);  // used for finding the elements of the subarray
        maxendinghere = max(arr[i],arr[i]+maxendinghere); 
        maxsofar = max(maxendinghere,maxsofar);
    }
    cout<<maxsofar<<"\n";
    auto it = myvec.begin(); // printing the subarray
    while (it != myvec.end())
    {
        cout<<*it<<"\t";
        it++;
    }
    cout<<"\n";
    return 0;

}

Now, I am trying to print the actual elements that form the subarray. One thing that I was able to think of was that the everytime (arr[i]+maxendinghere) will be greater than arr[i], a new element will be a part of the subarray and I push that in a vector and print the elements. But this doesn't give out the actual subarray correctly. What am I missing in this thought process? Thanks!

PS: I understand this is not the best coding style, but this was asked in an interview and I was trying to code it. I couldn't back then and hence this is what I was able to come up with.

Edit: Answer) I was able to code it up after the answer given by templatetypedef. The folllowing is the implementation.

//Largest Sum Contiguous Subarray
#include <iostream>
#include <map>
#include <vector>
#include <string>
#include <utility>
#include <algorithm>

using namespace std;

#define ll long long
#define pb push_back
#define mp make_pair
#define F(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define RF(i,a,b) for(int i = (int)(a); i >= (int)(b); i--)
#define SIZE 100000

int main (void)
{
    int currsum[SIZE],maxsumsofar[SIZE],sindex[SIZE],eindex[SIZE];
    int arr[SIZE];
    int start,end,n;
    cin>>n;
    F(i,0,n)
    {
        cin>>arr[i];
    }
    currsum[0] = arr[0];
    maxsumsofar[0] = arr[0];
    sindex[0] = 0;
    eindex[0] = 0;
    F(i,1,n)
    {
        if (arr[i] > (arr[i]+currsum[i-1])) // for starting index
            sindex[i] = i;
        else
            sindex[i] = sindex[i-1];

        currsum[i] = max(arr[i],arr[i]+currsum[i-1]);
        maxsumsofar[i] = max(currsum[i],maxsumsofar[i-1]);

        if (arr[i] > (arr[i]+currsum[i-1]))
            eindex[i] = i;
        else
        {
            if (maxsumsofar[i] == maxsumsofar[i-1])
                eindex[i] = eindex[i-1];
            else
                eindex[i] = i;
        }
    }
    cout<<maxsumsofar[n-1]<<"\n";
    F(i,0,n)
    {   
        if (maxsumsofar[i] == maxsumsofar[n-1])
        {
            start = sindex[i];
            end = eindex[i];
            break;
        }
    }
    cout<<"The array lies between indices "<<start<<" to "<<end<<"\n";
    return 0;
}

I would be very careful writing code like that in an interview - it's exceptionally hard to read. — templatetypedef
– templatetypedef, Commented Aug 5, 2017 at 12:35
@templatetypedef, I understand. I should take more meaningful variable names, and make it as descriptive as possible (avoiding use of preprocessors as well). It's just that, when I came back home, I tried to attempt the question myself and due to that, just coded it to make it work. — John Lui
– John Lui, Commented Aug 5, 2017 at 12:46

templatetypedef · Accepted Answer · 2017-08-05 12:34:15Z

1

Kadane's algorithm works by maintaining the start position of a subarray and repeatedly looking at the next element in the array and deciding to either

extend the subarray by appending that element, or
discarding the subarray and starting a new subarray after that element.

If you explicitly keep track of the start point of the current subarray (initially it's before the first element of the array, and it resets every time that the total drops below zero), it shouldn't be too hard to find the optimal subarray. Every time you update the maximum subarray found, you either

have just appended a new element to the existing maximum subarray (so just append to the best thing you've found so far), or
have found a new subarray that starts at a different position than the previous best subarray, so throw out the old max and replace it with this new one.

You can implement this by tracking not just the maximum subarray so far, but also its start position. You're in case (1) if the max subarray starts at the same position as your current array and case (2) otherwise.

answered Aug 5, 2017 at 12:34

templatetypedef

376k112 gold badges954 silver badges1.1k bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

John Lui Over a year ago

I believe it worked. I have been able to code it up and I am adding it in my original question. Thanks! :)

Collectives™ on Stack Overflow

Kadane's algorithm for printing the elements of the maximum subarray found?

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related