I recently took upon myself the challenge of finding the actual subsequence in an array that yields the largest sum rather than just the largest sum.

Example - if you enter {3,2,-5,4} in an array, my program returns {3,2}, since that yields the largest sum, 5.

I thought myself rather clever for this feat, until i noticed a specific error that was occurring that i am at a loss to explain.

To elaborate, if i enter specific numbers into the array, after the last number is entered, the program simply prints to the screen a large amount of seemingly unrelated numbers, and then terminates with "this program has stopped working etc." It is rather hard to describe exactly what goes wrong so here is an example of one of the array sequences that gave the error:
array size: 5
array numbers: {-9,-8,-7,4,-7}

I hope someone will take a look at this and help me find the mistake in my code. Perhaps it's a simple fix, or perhaps i've overcomplicated the whole thing. any advice or solution is appreciated. Thanks.

Here is the code:

/*this program finds the subsequence in a user-input array that yields the largest sum.*/

#include <iostream>
#include <numeric>
#define length(a) ( sizeof ( a ) / sizeof ( *a ) )

//Note: the program prints the FIRST subsequence that yields the largest sum, although there may be multiple subsequences of equal value.

using namespace std;


//prototypes

int summation(int a);  //given int n as paramter, returns: n+(n-1)+(n-2)+...+1.
                       //used to determine the length of an array that will store all
                       //possible ordered combinations in a user-input array.


int sequenceSums (int param[]);  //stores all possible subsequence sums of a user-input array in a new array and
                                 //returns the largest sum.



int FirstInLargest (int xyz, int param2[]); //finds the first element in the largest subsequence.
                                            //how it works: cycles through all subsequence sums and checks them against
                                            //the largest sum. returns the first element in the largest-valued
                                            //sequence if the largest sum is reached.

void SequenceNamer (int zyx, int param3[], int big); //prints the elements in the largest-valued sequence.
                                                     //starts at the first element and uses a sum counter that
                                                     //is checked against the largest sum. if the largest sum is
                                                     //reached, the program is terminated.

//global variables

int arraysize; //user-input array size that will be used in multiple functions; requires global scope.




//main
int main()
{   do {
    cout << "enter an array size: ";      //user inputs array size and elements
    cin >> arraysize; } while (arraysize<=0);
    int seq[arraysize], k=0;
    cout << "enter integers to be stored in array: " << endl;
    while (k<arraysize) {
    cin >> seq[k];
    k++; }

cout << "The subsequence that yields the largest sum is { ";

/*call to functions*/
int largestSum = sequenceSums (seq); //input user array, assign largestSum the return value
int firstinSequence = FirstInLargest(largestSum,seq); //input largestSum and user array, assign firstinSequence the return value
SequenceNamer (firstinSequence, seq, largestSum);  //input firstinSequence, user array and largestSum. after printing the
                                                   //subsequence elements, causes the program to terminate.
}
//end main


int sequenceSums (int param[]) {

int newSeq[summation(arraysize)];
int determine_start=0, arrayStart=arraysize;

for (int j=0;j<=arraysize; j++)
{
    partial_sum(param+j,param+arraysize,newSeq+determine_start);
    determine_start+=arrayStart;
    arrayStart-=1;
}

return *max_element(newSeq,newSeq+summation(arraysize));
}


int FirstInLargest (int xyz, int param2[]) {

signed int newSeq1[summation(arraysize)];
int determine_start1=0, arrayStart1=arraysize;

for (int j1=0;j1<=arraysize; j1++)
{
    partial_sum(param2+j1,param2+arraysize,newSeq1+determine_start1);

    for (int cycle_thru=0;cycle_thru<= length( newSeq1 ) ;cycle_thru++)
    {
        if (newSeq1[cycle_thru]==xyz) {return j1;}
    }
    determine_start1+=arrayStart1;
    arrayStart1-=1;
}
}


void SequenceNamer (int zyx, int param3[], int big) {

    int sumfinal=0;

    while (1) {
        cout << param3[zyx] << " ";
        sumfinal+=param3[zyx];
        if(sumfinal==big) {
            cout << "}" << endl << "The sum of this subsequence is " << big << ".";
            exit(1);
                          }
        zyx++;
    }
}


int summation (int a)
{
  if (a > 1)
   return (a + summation (a-1));
  else
   return (1);
}

Its a little hard for me to read the code it seems a bit messy(or maybe because im still a noob compared to others), it would be best to get the array size from the user and then after that add 1 to it and when you are getting input only let them type in one less than the max array size

cout << "enter an array size: "; //user inputs array size and elements
cin >> arraysize; } while (arraysize<=0);
int seq[arraysize+1]; 
int k = 0;
cout << "enter integers to be stored in array: \n";
while (k<arraysize-1) 
{
cin >> seq[k];
k++; 
}

see if that possibly solves the problem

Edited 5 Years Ago by L3gacy: n/a

Your symptoms are those of an array index overrun. Ie, when you loop over an array, you are going past the end of the array. You must make sure that you are respecting the size of the array, and the number of actually set elements in it. Review all instances of your accessing an array, and how you create, initialize, and populate it. You will find your problem.

P.S. Running in a debugger can help find this sort of problem. Once you see where it is happening, you will probably pull a "Homer" - doh!

Edited 5 Years Ago by rubberman: n/a

@L3gacy - if you examine my code carefully, you'll see that my method of user-input for array size and array elements works just fine. (but i admit wholeheartedly that this code is messy! and i'm certainly no advanced programmer or c++ master...)

I've actually got this fully working now!! :) ...one of the functions needed heavy remodeling. I'll leave it as an open challenge to figure out which one needs fixing and how...

@rubberman I came to that exact conclusion about 5 minutes ago...simply changed around some loop conditions (we won't say where) and voila!

but you speak of a "debugger" ...now i'm showing myself for the n00b i really am, but what exactly is that and how would i use it?

This is not Kadane's algorithm, is it? This algorithm makes multiple passes through the sequence including nested passes:

#include <limits>
#include <utility>

for (int j1=0;j1<=arraysize; j1++) // O(N)
{
     partial_sum(param2+j1,param2+arraysize,newSeq1+determine_start1); // O(N)

     for (int cycle_thru=0;cycle_thru<= length( newSeq1 ) ;cycle_thru++) // O( N*N)
     {
       // ...
     }
     
     // ...
}

Incidentally, this is not C++: int newSeq[summation(arraysize)]; The algorithm also used extra memory O(N*N); summation(N) yields N * (N+1) / 2.

Overall, it executes in cubic ( O(N*N*N) ) time and quadratic ( O(N*N) ) space.

Kadane's algorithm makes a single pass through the sequence, computing a running total of the maximum subsequence sum ending at that position. It executes in linear ( O(N) ) time and uses constant ( O(1) ) space.

Kadane's algorithm for an array of int:

// returns a pair of positions (the start and the end of the maximum sum subsequence) in array a
std::pair<std::size_t,std::size_t> find_max_sum_subsequence( const int a[], std::size_t N )
{
    int max_sum = std::numeric_limits<int>::min() ;
    std::size_t max_subseq_start_pos = 0 ;
    std::size_t max_subseq_end_pos = 0 ;

    int curr_max_sum = 0 ;
    std::size_t curr_subseq_start_pos = 0 ;
    std::size_t curr_subseq_end_pos = 0 ;
    for( ; curr_subseq_end_pos < N ; ++curr_subseq_end_pos )
    {
         curr_max_sum += a[curr_subseq_end_pos] ;

         if( curr_max_sum > max_sum )
         {
             max_sum = curr_max_sum ;
             max_subseq_start_pos = curr_subseq_start_pos ;
             max_subseq_end_pos = curr_subseq_end_pos ;
         }

         if( curr_max_sum < 0 )
         {
             curr_max_sum = 0 ;
             curr_subseq_start_pos = curr_subseq_end_pos + 1 ;
         }
    }
    return std::make_pair( max_subseq_start_pos, max_subseq_end_pos ) ;
}

Generalized Kadane's algorithm (any input sequence containing values belonging to a numeric type):

#include <iterator>
#include <iostream>
#include <limits>
#include <algorithm>
#include <list>

template< typename INPUT_ITERATOR >
void print_max_sum_subsequence( INPUT_ITERATOR begin, INPUT_ITERATOR end,
                                 std::ostream& stm = std::cout )
{
    typedef typename std::iterator_traits<INPUT_ITERATOR>::value_type numeric_type ;
    stm << "\nsequence: [ " ;
    std::for_each( begin, end,
                   [&stm] ( const numeric_type& v ) { stm << v << ' ' ; } ) ;
    stm << "]\n" ;

    numeric_type max_sum = std::numeric_limits<numeric_type>::min() ;
    INPUT_ITERATOR max_subseq_first = begin ;
    INPUT_ITERATOR max_subseq_last = begin ;
    const numeric_type ZERO = numeric_type() ;

    numeric_type curr_max_sum = ZERO ;
    INPUT_ITERATOR curr_subseq_first = begin ;
    for( INPUT_ITERATOR curr_subseq_last = begin ; curr_subseq_last != end ; ++curr_subseq_last )
    {
         curr_max_sum += *curr_subseq_last ;

         if( curr_max_sum > max_sum )
         {
             max_sum = curr_max_sum ;
             max_subseq_first = curr_subseq_first ;
             max_subseq_last = curr_subseq_last ;
         }

         if( curr_max_sum < ZERO )
         {
             curr_max_sum = ZERO ;
             curr_subseq_first = curr_subseq_last ;
             ++curr_subseq_first ;
         }
    }

    stm << "a maximum sum subsequence: [ " ;
    if( max_sum >= ZERO )
    {
        ++max_subseq_last ;
        std::for_each( max_subseq_first, max_subseq_last,
                       [&stm] ( const numeric_type& v ) { stm << v << ' ' ; } ) ;
        stm << "] (sum:" << max_sum << ")\n" ;
    }
    else stm << "] (the empty sequence)\n" ;
}

// print_max_sum_subsequence() is used like this:

template< typename T, std::size_t N > inline std::size_t size( T(&)[N] ) { return N ; }

int main()
{
    const int a[] = { -9, 88, -17, -40, 72, -3, 6, -7, 5, -2 } ;
    print_max_sum_subsequence( a, a+size(a) ) ;

    std::list<double> seq( size(a) ) ;
    std::transform( a, a+size(a), seq.begin(), [] ( double d ) { return d + 4.3 ; } ) ;
    print_max_sum_subsequence( seq.rbegin(), seq.rend() ) ;
}

Looks like you are making progress. I don't have time to analyze vijayan121's post yet, but from a glance it should help with performance issues. As for debuggers, it depends upon the compiler and platform. If you are using the GNU compiler suite, there is gdb as well as some GUI front-ends for that, including Eclipse. If you are using Microsoft Visual Studio compilers, then that has a debugger as well. When you compile your code for debugging (-g compiler option), then the symbols are left in the resulting object code, as well as source location information (source files and line numbers). That allows you to do things like set break points at certain locations in your code in order to examine variables, analyze behavior, etc. Anyway, these are tools that every programmer needs. Diagnostic trace statements are inadequate for all but the most rudimentary debugging purposes.

@vijayan121 i understand that my program takes up unnecessary memory and time, but it will take me some time to decipher the code you've given as i am unfamiliar with some of the elements in your code (thanks to my n00b status). but thanks for giving the more efficient version of what i was trying to do (i.e., kadane's actual algorithm rather than just kadane's result)

This article has been dead for over six months. Start a new discussion instead.