Random commentary about C++, STL, Boost, Perl, Python, Algorithms, Problem Solving and Web Search

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

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

ReplyDeleteThe solution could be:

ReplyDeleteint 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.

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

}