Antonio Gulli's coding playground

Here is an excellent blog post on this topic http://wordaligned.org/articles/the-maximum-subsequence-problem

The solution could be:

int vect[] = {1,1,2,1,1,1,1,3,3,3,2};

int cont_seq_sum(int vect[], int size)
{
int sum = vect[0];
int max = sum;
for (int i=0; i max )
max = sum;
}
return max;
}

int main( int argc, char* argv[] )
{
std::cout << max_cont_seq(vect,sizeof(vect)/sizeof(int)) << std::endl;
std::cout << cont_seq_sum(vect,sizeof(vect)/sizeof(int)) << std::endl;
return 0;
}

I guess you contented in reading the book Programming Pearls by Bentley. One column was dedicated to this algorithm. I am providing the code.

int max_subarray_kadane_algo(int array[], int size)
{
int max_sofar = 0;
int max_ending_here = 0;
int index;

for(index = 0; index < size; index++)
{
max_ending_here = max(0, max_ending_here + array[index]);
max_sofar = max(max_sofar, max_ending_here);

// Visulise the algorithm
cout << "Element " << array[index] << endl;
cout << "max_ending_here " << max_ending_here << endl;
cout << "max_sofar " << max_sofar << endl << endl;
}

return max_sofar;
}

int main()
{
// Exercise problem from Algorigthms by Das Gupta
int data[] = {5, 15, -30, 10, -5, 40, 10};

int size = sizeof(data)/sizeof(data[0]);

cout << "Result " << max_subarray_kadane_algo(data, size);
}