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);
}
